反转链表的每个k个节点

Question

我正在准备进行技术面试,我坚持编写这个程序来反转链表的每个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 && count<c)
 {
  count++;
  temp=root->link;
  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 && count<c)
 {

    count++;
    prev=first->link;
    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 && count<c)
    {   
     printf("inside while: %c\n",n->data);  // 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;
}

Answer 1

是的,我从未成为递归的粉丝,所以这是我使用迭代的镜头:

  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;
 }

Answer 2

我喜欢你的递归，尽管它可能不是最好的解决方案。从你的代码看出你设计的时候考虑得很深。您距离答案仅一步之遥。

原因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;