递归反转链表时出现问题

Question

为什么这段反转链表的代码不起作用？我想确切地知道我做错了什么。

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

当我试运行时，它似乎工作正常，但随后给出了 TLE。

Answer 1

您的反向函数有两个明显的问题：

• 当链表有多个节点时，就会引入环。这意味着，如果有代码不期望循环，而只是天真地迭代结果列表的所有节点，那么它将进入无限循环。这可以解释您收到的时间限制错误。

• 它返回列表的原始头部。相反，它应该返回原始列表的tail，因为这将是反转列表的第一个节点。

让我们举一个简单的例子，链表只有两个节点，值为 1 和 2。然后当调用

reverseList

时，我们可以像这样可视化状态：

 head
  ↓
┌────────────┐     ┌────────────┐
│ val: 1     │     │ val: 2     │
│ next: ──────────►│ next: NULL │
└────────────┘     └────────────┘ 

然后我们进行递归调用，其中传递对第二个节点的引用作为参数。在该递归调用中，该指针是

head

。我在这里称之为

head'

（带撇号）：

 head               head'
  ↓                  ↓
┌────────────┐     ┌────────────┐
│ val: 1     │     │ val: 2     │
│ next: ──────────►│ next: NULL │
└────────────┘     └────────────┘ 

这里我们遇到了基本情况，因此递归调用返回对第二个节点的引用，该节点在调用上下文中被分配给

p

：

 head                p
  ↓                  ↓
┌────────────┐     ┌────────────┐
│ val: 1     │     │ val: 2     │
│ next: ──────────►│ next: NULL │
└────────────┘     └────────────┘ 

然后执行

p->next=head

，我们得到：

     head                p
      ↓                  ↓
    ┌────────────┐     ┌────────────┐
    │ val: 1     │     │ val: 2     │
 ┌─►│ next: ──────────►│ next: ─┐   │
 │  └────────────┘     └────────│───┘ 
 └──────────────────────────────┘

创建了一个循环。现在，当执行

return head

时，我们看到出现了两个问题：返回了错误的节点引用，并且循环没有被破坏。

以下改编代码纠正了这两个问题：

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    struct ListNode* newHead = reverseList(head->next);
    // The tail of the recursively reversed list is at head->next.
    //    Append the current node (head) at that tail
    head->next->next = head;
    // And terminate the list at the new tail:
    head->next = NULL;
    // Return the new head, not the old head
    return newHead;
}