递归反转Linked List的工作原理是什么？附C++代码解析

先看给定的C++实现代码：

ListNode* reverseListRecursive(ListNode* head)
{
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *temp = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return temp;
}

核心逻辑拆解 #

递归反转的本质是先处理子链表，再调整当前节点的指针，分四个关键步骤：

1. 递归终止条件

当head为空（空链表），或者head->next为空（当前节点是原链表的最后一个节点），直接返回head。这个返回值就是反转后链表的新头节点——因为原链表的最后一个节点会变成反转后的第一个节点。

2. 递归深入：拆解子问题

每次调用reverseListRecursive(head->next)，相当于把当前节点的下一个节点作为新的头，去反转剩下的子链表。比如原链表是1->2->3->4，调用reverseListRecursive(1)时，会先递归处理2->3->4，再处理3->4，直到最后处理4。

3. 回溯阶段：调整指针

当递归调用返回后，我们拿到了子链表反转后的头节点temp，此时需要调整当前节点的指针：

• head->next->next = head：把当前节点的下一个节点（也就是反转后子链表的尾节点）的next指向当前节点，完成局部反转。比如处理节点3时，head->next是4，这行代码会让4->next = 3。
• head->next = NULL：把当前节点的next设为空，让它成为新的子链表的尾节点。比如节点3的next设为空后，3就变成了4->3这个子链表的尾。

4. 返回新头节点

每次递归返回的temp都是反转后整个链表的头节点（始终是原链表的最后一个节点），所以最终函数返回的就是反转后的完整链表的头。

用实例走一遍流程 #

假设原链表是1->2->3->4->NULL：

1. 调用reverseListRecursive(1)，因1->next不为空，递归调用reverseListRecursive(2)
2. 调用reverseListRecursive(2)，递归调用reverseListRecursive(3)
3. 调用reverseListRecursive(3)，递归调用reverseListRecursive(4)
4. 调用reverseListRecursive(4)，满足终止条件，返回4给上一层的temp
5. 回到reverseListRecursive(3)：执行4->next = 3，3->next = NULL，返回4
6. 回到reverseListRecursive(2)：执行3->next = 2，2->next = NULL，返回4
7. 回到reverseListRecursive(1)：执行2->next = 1，1->next = NULL，返回4
8. 最终得到反转后的链表4->3->2->1->NULL

内容的提问来源于stack exchange，提问作者random_user