206. 反转链表

LeetCode 原题链接 image.png

实现思路

两个两个依次交换，交换的时候需要有一个临时变量记录剩下的链表，交换完成后将 pre 和 cur 向后移动一位，继续交换，直到 cur 为空。

  • 定义两个指针 pre 和 cur，pre 初始化为 null，cur 初始化为 head。
  • 遍历链表，将 cur 的 next 指向 pre，然后将 pre 和 cur 向后移动一位。
  • 遍历结束后，pre 指向新的链表头节点。

代码实现

var reverseList = function (head) {
  let pre = null;
  let cur = head;

  while (cur !== null) {
    let temp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = temp;
  }

  return pre;
};

易错点：反转链表不需要虚拟头节点

普通链表反转不需要虚拟头节点。反转过程中，pre 本身就在维护“已经反转部分”的头节点；循环结束后，pre 也正好是整个链表的新头节点。

初始状态下：

已反转部分       未处理部分
pre              cur
 ↓                ↓
null             1 -> 2 -> 3 -> null

每轮循环把 cur 指向的节点移动到已反转部分的头部：

第 1 轮：1 -> null          2 -> 3 -> null
第 2 轮：2 -> 1 -> null     3 -> null
第 3 轮：3 -> 2 -> 1        null

原链表头节点 1 反转后会成为尾节点，所以第一次执行 cur.next = pre 时，应该让 1.next 指向 null。这正是将 pre 初始化为 null 的原因。

错误写法一：在循环内部初始化 pre

var reverseList = function (head) {
  const dummy = new ListNode(null, head);
  let p = dummy;

  while (p.next) {
    let pre = null;
    let cur = p.next;

    const temp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = temp;

    p = p.next;
  }

  return dummy.next;
};

这段代码每轮只处理一个节点，并且每次都会将 pre 重新设置为 null。以 1 -> 2 -> 3 为例，第一轮执行 cur.next = pre 后，链表会被拆成：

dummy -> 1 -> null

2 -> 3 -> null

随后 p 移动到节点 1，由于 p.next 已经是 null，循环直接结束。后面的 2 -> 3 不仅没有被反转，还与返回结果断开了。

此外，cur = temp 也没有发挥作用，因为本轮循环马上结束；即使存在下一轮，cur 也会在循环内部被重新声明。

错误写法二：让 pre 指向虚拟头节点

var reverseList = function (head) {
  const dummy = new ListNode(null, head);

  let pre = dummy;
  let cur = head;

  while (cur) {
    const temp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = temp;
  }

  return dummy.next;
};

假设原链表为 1 -> 2 -> 3，初始时：

dummy -> 1 -> 2 -> 3 -> null
  ↑      ↑
 pre    cur

第一次执行：

cur.next = pre;

就会同时出现：

dummy.next = 1
1.next = dummy

因此 dummy 和节点 1 形成了环：

dummy -> 1
  ↑      |
  └──────┘

而且 dummy.next 始终指向原头节点 1。循环结束后，真正的新头节点是 pre 指向的节点 3，返回 dummy.next 不但返回了错误节点，还会得到一个带环的链表。

正确写法的三个关键点

  • pre 必须定义在循环外，保存整个反转过程中已经处理好的链表。
  • pre 必须初始化为 null，确保原头节点最终成为正确的尾节点。
  • 循环结束后必须返回 pre，因为它指向反转后的新头节点。

虚拟头节点通常适合删除节点、在头部插入节点等需要统一处理头节点的场景。反转链表已经可以用 pre 接住不断变化的新头节点，引入虚拟头节点不会简化逻辑，使用不当反而容易产生环或返回错误节点。