c - 试图理解这种递归
问题描述
我需要一个链表并返回它的镜像版本,这里是一个例子
输入:1->2->3->4->5->null。
结果:1->2->3->4->5->5->4->3->2->1->NULL。
我只需要访问每个节点一次
我设法解决了它,但我真的无法理解解决方案,所以任何人都可以帮我分解镜像功能吗?
我的代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node* next;
} node;
void PushEnd(node** headRef, int data)
{
node* newnode = malloc(sizeof(node));
if (!newnode)
return;
newnode->data = data;
if (*headRef == NULL)
{
newnode->next = NULL;
*headRef = newnode;
}
else
{
node* current = *headRef;
node* prev;
while (current->next)
{
current = current->next;
}
current->next = newnode;
newnode->next = NULL;
}
}
void printList(node* head)
{
if (head == NULL)
return;
printf("%d ", head->data);
printList(head->next);
}
node* mirror(node* head)
{
node* new = NULL;
if (head == NULL)
return NULL;
PushEnd(&new,head->data);
new->next=mirror(head->next);
PushEnd(&new, head->data);
return new;
}
void Test()
{
node* head = NULL;
int a[] = {10,50,19,54,30};
for (int i = 0; i < (sizeof(a) / sizeof(int)); i++)
{
PushEnd(&head, a[i]);
}
printList(head);
printf("\n");
node* new = mirror(head);
printList(new);
}
int main()
{
Test();
return 0;
}
使用这个调用:new->next=mirror(head->next); 它如何推动第一个元素?
提前致谢
解决方案
在函数的第一次调用中,指针new
等于 NULL。然后 PushEnd
调用该函数。
PushEnd(&new,head->data);
所以现在结果列表看起来像(如果使用数组中的数据)
| 10 | NULL |
^
|
new
然后函数本身递归调用(例如对于值为 50 的数组元素)
new->next=mirror(head->next);
退出此调用后,由于在上面的语句中分配给指针 new->next,您将拥有
| 10 | ->50 | -> | 50 | ...| -> ... | ...| NULL|
^
|
new
现在值 10 被附加到列表的尾部
PushEnd(&new, head->data);
你会有
| 10 | ->50 | -> | 50 | ...| -> ... | ...| ->10 | -> | 10 | NULL |
^
|
new
这种方法由于调用了函数而效率低下,PushEnd
因为它需要遍历整个新构建的列表才能实现它的尾部。
推荐阅读
- .net-core - 具有多个配置文件和环境的 Ocelot
- powershell - 为什么 Write-Error 会终止脚本?
- android - 如何根据颤动中文本小部件的索引将多个文本小部件的数据传递给字符串列表
- xml - 为什么我的 XSL 样式表不能与我的 XML 一起使用?
- r - 类 tibble 的 Tibble 列而不是类数据框
- javascript - 无法将地图中的项目参数传递给 onClick
- node.js - 邮件因涉嫌垃圾邮件 Nodejs、Yandex、Firebase 功能而被拒绝
- firebase - Cloud Function 自动终止
- django - 根据模型的数量在 django 模板中使用特定的引导列
- javascript - 如何通过单击按钮更改 Javascript 中的 src 来更改多个图像