我正在尝试使用递归反转链表并为其编写了以下代码。该列表是列表的开头。
node *reverse_list_recursive(node *list)
{
node *parent = list;
node *current = list->next;
if(current == NULL)
return parent;
else
{
current = reverse_list_recursive(current);
current->next = parent;
printf("\n %d %d \n",current->value,parent->value);
return parent;
}
}
我可以看到所有链接都被反转了。但是,当我尝试显示时,我得到了无限的数字打印。当我试图反转列表中最初的第一个数字的链接时,我怀疑有错误。
我做错了什么?
最佳答案
假设我有一个链表:
---------- ---------- ---------- ----------
| 1 | |--->| 2 | |--->| 3 | |--->| 4 | |--->NULL
---------- ---------- ---------- ----------
您的代码将其转换为:
---------------------- ----------------------
| | | |
v | v |
---------- ---------- ---------- ----------
| 1 | |--->| 2 | | | 3 | | | 4 | |
---------- ---------- ---------- ----------
^ |
| |
----------------------
注意第一个元素仍然指向 2。
如果在前两个之后添加 parent->next = NULL
行,您将得到:
---------------------- ----------------------
| | | |
v | v |
---------- ---------- ---------- ----------
NULL<---| 1 | | | 2 | | | 3 | | | 4 | |
---------- ---------- ---------- ----------
^ |
| |
----------------------
这实际上是正确的结构。
完整代码为:(每次递归调用只需要打印当前值即可)
node *reverse_list_recursive(node *list)
{
node *parent = list;
node *current = list->next;
if(current == NULL)
return parent;
else
{
current = reverse_list_recursive(current);
parent->next = NULL;
current->next = parent;
printf("\n %d \n",current->value);
return parent;
}
}
关于c - 反向链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4078864/