1

我正在解决在给定大小的组中反转链表的问题，我使用的算法如下：

1) 反转大小为 k 的第一个子列表。在反转时，我保留了下一个节点和前一个节点的轨迹。让指向下一个节点的指针为 next，指向前一个节点的指针为 prev & 指向当前节点的指针为 ptr。

2) head = reverse(next, k)-递归调用列表的其余部分

3）返回prev，它是反向列表的新头

我的代码示例是：

struct node *reverse(struct node *start,int k)
{
    struct node *prev,*ptr,*next;
    prev=NULL;
    ptr=start;
    int count=0;
    while(count<k && ptr!=NULL)
    {
        next=ptr->link;
        ptr->link=prev;
        prev=ptr;
        ptr=next;
        count++;
    }

    if(next!=NULL)//recursive call
    start=reverse(next,k);

    return prev;
}

但是我的输出只是反转了列表的前半部分！

例如：如果我的清单是：98 74 94 857 8 7

    My output is : 94 74 98(The rest is not being displayed)

我哪里错了？..这种方法正确吗？

4

2 回答 2

3

当您进行递归调用时：

if(next!=NULL)//recursive call
  start=reverse(next,k);

return prev;

您将递归调用的结果保存在 中start，您再也不会引用它。当控制权从函数传递过来时，指针就会过期，并且递归调用的结果（即第一个k元素之外的任何内容）都会丢失。在返回之前，您必须将这些结果附加到反向子列表中。

于 2013-05-09T03:39:58.350 回答
0 
if(next!=NULL)//recursive call
 start->next=reverse(next,k);

return prev;

这将在下一个存储第 (k+1) 个节点的位置时起作用。当我们开始->下一个 (k+1) 个节点成为新的头和

于 2018-03-15T19:04:45.670 回答