206. 反转链表

206. 反转链表 - 力扣（LeetCode）

class Solution {
public:
  ListNode* reverseList(ListNode* head) {
	// XXX Don't set a dummy here!
	// ListNode Dummy(0, head), *Prev = &Dummy;
    ListNode *Prev = nullptr;
    while (head) {
      ListNode *Next = head->next;
      head->next = Prev;
      Prev = head;
      head = Next;
    }
    return Prev;
  }
};

迭代法其实用不着设置一个 dummy 节点，因为你会发现我们这里并没有针对 Prev->next 的操作。事实上，如果你设置了一个 dummy 节点但却没有及时更新 Dummy.next 的值的话，ASan 反而会报错，因为你返回的是一个临时栈上变量！

迭代法在某个时刻的状态基本上就如下图所示。注意最开头的节点指向的 nullptr，它正是我们把 Prev 用 nullptr 进行初始化的结果，这一点很重要。

Pasted image 20260313122353.png

class Solution {
public:
  ListNode* reverseList(ListNode* head) {
    if (!head || !head->next)
      return head;

    ListNode *Reversed = reverseList(head->next);
    // At this point, head->next is still the FORWARD next!
    ListNode *Tail = head->next->next;
    head->next->next = head;
    // This is just for demonstration. you can just write head->next = nullptr;
    head->next = Tail;
    return Reversed;
  }
};

理解递归法非常重要的一点就在于要意识到，在执行了 reverseList(head->next) 之后，head 以后的节点都已经倒序连接，但当前函数栈当中的 head->next 仍然是正序后继节点！

比如，在末尾的两个节点被处理完毕后，整个链表显示出这样的结构：

Pasted image 20260313121703.png

正因为 head->next 事实上直接指向正序后继节点，也即倒序尾节点，我们就可以利用多出来的这部分信息，快速地将倒序尾节点连接在 head 上。

二刷

其实本题最关键的问题在于初始态的定义。实际上，初始态的 Prev 应该指向的是 nullptr，而不是像通常思维当中指向 head，如下图所示。

Pasted image 20260831111652.png