扭转链表每k个节点 [英] Reverse every k nodes of a linked list

问题描述

我是preparing的技术面试，我停留在写这个程序来扭转链表每k节点。

例如

  1→2→3→4- GT; 5→6 //链表
2→1→4- GT; 3→6-→5 //输出对于k = 2
 

编辑：

下面是我的code。我只得到6> 5的输出。

 结构节点* recrev（结构节点*诺德，INT C）
{
 结构节点*根=诺德，*温度，*最后，* preV = NULL;
 诠释计数= 0;
 而（根= NULL和放大器;！＆安培;计数c为C）
 {
  算上++;
  TEMP =根 - ＆GT;链接;
  根 - ＆GT;链接= preV;
  preV =根;
  根=温度;
 }
 如果（临时！= NULL）
   noode-＆GT;链接= recrev（温度，C）;
 其他
   返回preV;

}
 

任何帮助是AP preciated。谢谢你。

编辑：我试图执行叶兰齐默尔曼的算法如下

 结构节点*转（结构节点*根，INT C）
{
 结构节点*首先=根，* preV，*其余= NULL;
 诠释计数= 0;
 而（第一= NULL和放大器;！＆安培;计数c为C）
 {

    算上++;
    preV =一线＆GT;链接;
    第一代＆GT;链接=剩余;
    第一剩余=;
    第一= preV;
 }
 返回剩下的;
}
结构节点* RECC（结构节点*根，INT C）
{
 结构节点*最后，*温度，* N =根，* T;
 诠释计数= 0;
 而（N！= NULL）
 {
       计数= 0;
       临时= REV（N，C）;
       最后=温度;


    而（N = NULL和放大器;！＆安培;计数c为C）
    {
     的printf（里，而：％C \ N，正＆GT;数据）; //这会打印一次
     如果（N-＆GT;链接== NULL）的printf（空）; //在第一次迭代本身NULL被印
        N = N-＆GT;链接;
        最后= final-＆GT;链接;
        算上++;
    }

 }
 final-＆GT;链接= NULL;
 返回决赛;
}
 

解决方案

我喜欢你递归，虽然可能不是最好的解决方案。我可以从你的code，你认为它深，当你设计它看到的。您只差一个步骤就可以了答案。

原因：您流连忘返新根节点的递归情况

 如果（温度！= NULL）
   noode-＆GT;链接= recrev（温度，C）;
   //你需要回到这里的新的根节点
   //在这种情况下是$ P $光伏：
   //返回preV;
 其他
   返回preV;
 

I am preparing for a technical interview and I am stuck at writing this program to reverse every k nodes of a linked list.

For example

1->2->3->4->5->6 //Linked List
2->1->4->3->6->5 //Output for k=2

EDIT:

Here is my code. I get only 6->5 as output.

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;

}

Any help is appreciated. Thanks.

EDIT: I tried to implement Eran Zimmerman's Algorithm as below.

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

解决方案

I like you recursion, although it may be not the best solution. I can see from your code that you think it deep when you design it. You're just one step away from the answer.

Cause: You forget to return the new root node in your recursion case.

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;

这篇关于扭转链表每k个节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！