c - 在c中递归地反转链表

Question

当 head 作为参数发送给它时，以下代码可以正常工作。由于我是 C 的新手，所以我无法理解它是如何工作的。请帮帮我。

struct node *recursiveReverseLL(struct node *list)
{
    struct node *revHead;
    if (list == NULL || list->link == NULL)
    {
        return list;
    }

    revHead = recursiveReverseLL(list->link);
    list->link->link = list;
    list->link = NULL; 

    return revHead;
}

我不知道如何使用这些递归调用提供链接。即)如果链接是，

1 -> 2 -> 3 -> 4 

那么hw是不是改成了，

4 -> 3 -> 2 -> 1

Answer 1

一般的递归算法是:

1. 将列表分成2部分——首先节点和列表的其余部分。
2. 为 rest 递归调用 reverse链表。
3. 将 rest 链接到 first。
4. 修复head指针

这是带有内联注释的代码:

struct node* recursiveReverseLL(struct node* first){

   if(first == NULL) return NULL; // list does not exist.

   if(first->link == NULL) return first; // list with only one node.

   struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.

   first->link->link = first; // make first; link to the last node in the reversed rest.

   first->link = NULL; // since first is the new last, make its link NULL.

   return rest; // rest now points to the head of the reversed list.
}

我希望这张照片能让事情更清楚:

_{(来源:geeksforgeeks.org)}
.