试图理解这种递归

Question

我需要一个链表和return它的镜像版本，这里是一个例子

输入：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); 它如何推动第一个元素？

提前致谢

Answer 1

在函数的第一次调用中，指针 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，这种方法效率低下，因为它需要遍历整个新建列表来实现它的尾部。

试图理解这种递归

trying to understand this recursion

c

recursion

linked-list

singly-linked-list

function-definition