反转链表的每个k个节点
我正在准备进行技术面试，我坚持编写这个程序来反转链表的每个k节点。
例如
1->2->3->4->5->6 //Linked List 2->1->4->3->6->5 //Output for k=2 编辑：
这是我的代码。 我得到的输出只有6-> 5。
struct node* recrev(struct node* noode,int c) { struct node* root=noode,*temp,*final,*prev=NULL; int count=0; while(root!=NULL && countlink; root->link=prev; prev=root; root=temp; } if(temp!=NULL) noode->link=recrev(temp,c); else return prev; }
任何帮助表示赞赏。 谢谢。
编辑：我试图实现Eran Zimmerman的算法如下。
struct node* rev(struct node* root,int c) { struct node* first=root,*prev,*remaining=NULL; int count=0; while(first!=NULL && countlink; first->link=remaining; remaining=first; first=prev; } return remaining; } struct node* recc(struct node* root,int c) { struct node* final,*temp,*n=root,*t; int count=0; while(n!=NULL) { count=0; temp=rev(n,c); final=temp; while(n!=NULL && countdata); // This gets printed only once if(n->link==NULL) printf("NULL"); //During first iteration itself NULL gets printed n=n->link; final=final->link; count++; } } final->link=NULL; return final; }
我喜欢你的递归，虽然它可能不是最好的解决方案。 我可以从你的代码中看到你在设计它时认为它很深。 你离答案只有一步之遥。
原因 ：您忘记在递归情况下返回新的root 。
if(temp!=NULL) noode->link=recrev(temp,c); // You need return the new root node here // which in this case is prev: // return prev; else return prev;
是的，我从来不是一个递归的粉丝，所以这是我使用迭代的镜头：
public Node reverse(Node head, int k) { Node st = head; if(head == null) { return null; } Node newHead = reverseList(st, k); st = st.next; while(st != null) { reverseList(st, k); st = st.next; } return newHead } private Node reverseList(Node head, int k) { Node prev = null; Node curr = head; Node next = head.next; while(next != null && k != 1){ curr.next = prev; prev = curr; curr = next; next = next.next; --k; } curr.next = prev; // head is the new tail now. head.next = next; // tail is the new head now. return curr; }
这是一个伪代码。
temp = main_head = node.alloc (); while ( !linked_list.is_empty () ) { push k nodes on stack head = stack.pop (); temp->next = head; temp = head; while ( !stack.empty () ) { temp->next = stack.pop (); temp = temp->next; } }
我已经对此代码进行了演示实现。 原谅凌乱的实施。 这适用于k任何值。 每个k大小的段在内环中单独反转，并且不同的段在进入内环之前在外环中彼此链接。 temp跟踪k大小的子列表的最后一个节点， head保存下一个子列表的下一个值，然后我们链接它们。 显式堆栈用于执行反转。
#include #include typedef struct _node { int a; struct _node *next; } node_t; typedef struct _stack { node_t *arr[128]; int top; } stack_t; void stk_init (stack_t *stk) { stk->top = -1; } void push (stack_t *stk, node_t *val) { stk->arr[++(stk->top)] = val; } node_t *pop (stack_t *stk) { if (stk->top == -1) return NULL; return stk->arr[(stk->top)--]; } int empty (stack_t *stk) { return (stk->top == -1); } int main (void) { stack_t *stk = malloc (sizeof (stack_t)); node_t *head, *main_head, *temp1, *temp; int i, k, n; printf ("\nEnter number of list elements: "); scanf ("%d", &n); printf ("\nEnter value of k: "); scanf ("%d", &k); /* Using dummy head 'main_head' */ main_head = malloc (sizeof (node_t)); main_head->next = NULL; /* Populate list */ for (i=n; i>0; i--) { temp = malloc (sizeof (node_t)); temp->a = i; temp->next = main_head->next; main_head->next = temp; } /* Show initial list */ printf ("\n"); for (temp = main_head->next; temp != NULL; temp = temp->next) { printf ("%d->", temp->a); } stk_init (stk); /* temp1 is used for traversing the list * temp is used for tracing the revrsed list * head is used for tracing the sublist of size 'k' local head * this head value is used to link with the previous * sublist's tail value, which we get from temp pointer */ temp1 = main_head->next; temp = main_head; /* reverse process */ while (temp1) { for (i=0; (temp1 != NULL) && (inext; } head = pop (stk); temp->next = head; temp = head; while (!empty (stk)) { temp->next = pop (stk); if (temp->next == NULL) break; temp = temp->next; } } /* Terminate list with NULL . This is necessary as * for even no of nodes the last temp->next points * to its previous node after above process */ temp->next = NULL; printf ("\n"); for (temp = main_head->next; temp != NULL; temp = temp->next) { printf ("%d->", temp->a); } /* free linked list here */ return 0; }
我会做这样的事情：
init curr (node pointer) to point to the beginning of the list. while end of list is not reached (by curr): - reverse(curr, k) - advance curr k times
and reverse是一个从curr开始反转前k个元素的函数。
这可能不是最优雅或最有效的实现，但它的工作原理非常简单。
回答你添加的代码：
你回来了prev，这是不断进步的。 你应该返回列表的开头。
（我假设这是一个单链表。）你可以保留一个临时指针（让我们称之为nodek ）并在while循环中前进k次。 这将需要O（k）。 现在，您有一个指向列表开头和子列表最后一个元素的指针。 要在此处反转，请从头部移除O（1）并添加到nodek ，即O（1）。 对所有元素执行此操作，因此再次为O（k）。 现在将root更新到nodek，再次在nodek上运行while循环（获取nodek的新位置）并再次重复整个过程。 记得在整个过程中进行任何错误检查。 该解决方案将在O（n）处运行，仅有O（1）额外空间。
以下解决方案使用额外的空间来存储指针，并分别反转每个列表的大小。 最后，建立了新的列表。 当我测试时，这似乎涵盖了边界条件。
template struct Node { T data; struct Node* next; Node() { next=NULL; } }; template void advancePointerToNextChunk(struct Node * & ptr,int & k) { int count =0; while(ptr && count next; count ++; } k=count;} /*K-Reverse Linked List */ template void kReverseList( struct Node * & head, int k){ int storeK=k,numchunk=0,hcount=0; queue < struct Node *> headPointerQueue; queue *> tailPointerQueue; struct Node * tptr,*hptr; struct Node * ptr=head,*curHead=head,*kReversedHead,*kReversedTail; while (ptr) { advancePointerToNextChunk(ptr,storeK); reverseN(curHead,storeK,kReversedHead,kReversedTail); numchunk++; storeK=k; curHead=ptr; tailPointerQueue.push(kReversedTail),headPointerQueue.push(kReversedHead); } while( !headPointerQueue.empty() || !tailPointerQueue.empty() ) { if(!headPointerQueue.empty()) { hcount++; if(hcount == 1) { head=headPointerQueue.front(); headPointerQueue.pop(); } if(!headPointerQueue.empty()) { hptr=headPointerQueue.front(); headPointerQueue.pop(); } } if( !tailPointerQueue.empty() ) { tptr=tailPointerQueue.front(); tailPointerQueue.pop(); } tptr->next=hptr; } tptr->next=NULL;} template void reverseN(struct Node * & head, int k, struct Node * & kReversedHead, structNode * & kReversedTail ) { struct Node * ptr=head,*tmp; int count=0; struct Node *curr=head,*nextNode,*result=NULL; while(curr && count next; curr->next=kReversedHead; kReversedHead=curr; if(count ==1 ) kReversedTail=kReversedHead; curr=nextNode; }}
public class ReverseEveryKNodes { private static class Node { private K k; private Node next; private Node(K k) { this.k = k; } } private Node head; private Node tail; private int size; public void insert(K kk) { if(head==null) { head = new Node (kk); tail = head; } else { tail.next = new Node (kk); tail = tail.next; } size++; } public void print() { Node temp = head; while(temp!=null) { System.out.print(temp.k+"--->"); temp = temp.next; } System.out.println(""); } public void reverse(int k) { head = reverseK(head, k); } Node reverseK(Node n, int k) { if(n==null)return null; Node next=n, c=n, previous=null; int count = 0; while(c!=null && count r = new ReverseEveryKNodes(); r.insert(10); r.insert(12); r.insert(13); r.insert(14); r.insert(15); r.insert(16); r.insert(17); r.insert(18); r.print(); r.reverse(3); r.print(); } }