C++递归反向链表为什么有效？

Question

这就是问题所在:https://leetcode.com/problems/reverse-linked-list/

我知道解决方案(它在互联网上到处都是复制粘贴的)，但我不明白它的一部分是如何工作的...所以:

    struct ListNode{
        int data;
        ListNode* next;
    };

   ListNode* reverseList(ListNode* head) {
        if (!head || !(head -> next)) {
            return head;
        }
        ListNode* node = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return node;
    }

这有效。

现在我通过调试器得到它并看到我不明白的东西......

假设我们有一个链表:

1->2->3->NULL

1 ) 我们已将最后一个 3->Null 部分传递给 ListNode* node = reverseList(head->next);它确实 return head; 现在 ListNode* node = 3->NULL;

好的，node == 3->NULL 和 head == 2->3->NULL

2 ) 让我们跳到 head->next->next = head:

现在 head == 2->3->2->3... 但是为什么 node == 3->2->3->2... ???

它们是如何连接的？我在这里完全糊涂了。

3) 在下一行 head -> next = NULL 我们可以看到它再次影响 head 和 node :

如您所见，我不明白node 和head 之间的联系。所以我不明白它是如何工作的，我觉得我不明白这些链表通常是如何工作的。也许有人可以帮助我？欣赏它。

Answer 1

不幸的是，我没有足够的声誉来发表评论，所以我要发表一个答案，希望它能帮助你。我将使用绘画图片来使事情更容易可视化。让我们开始吧:

假设我们有列表 1->2->3-> 所以它是这样开始的:

现在我们开始这个函数，它一直运行到第一个递归，它以一个新的头开始，我们有以下情况:

然后函数再次运行，结果如下:

然后我们从一个新的 head (3) 开始，但这里最后一个函数返回 head 因为 if 条件 head->next == NULL 被满足。所以我们有:

然后我们跟随函数直到结束改变 head->next->next = head 和 head->next = NULL 所以我们有:

然后函数返回节点，我们回到原来的调用。然后我们执行相同的步骤，最后得到:

最后函数返回节点，所以我们得到:

希望这对您有所帮助，并对答案质量不佳深表歉意，但我发现在可视化递归时更容易解决递归问题，最简单的可视化方法是绘制。