LeetCode 反转链表双指针题解

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路

将 n + 1 的 next 指向 n
反转多个节点：双指针遍历链表，重复操作

反转链表的本质是把每个节点的 next 反向。不需要移动节点、也不需要重新分配内存，只改指针的指向就够了，这也是它空间复杂度能做到 O(1) 的原因。

难点在于改指针会破坏链表的连通性。单链表里，一个节点的 next 是通往后面所有节点的唯一通路，一旦把它改成指向前一个节点，后半部分就彻底找不到了。所以必须在改之前先把后继保存下来，这就是代码里那个 tmp 的作用。

用两个指针的分工是：p1 指向当前正在处理的节点，p2 指向已经反转好的那部分的头部。每一轮把 p1 的 next 接到 p2 上，然后两个指针整体往后挪一位。可以想象成链表被切成两段，左边是已反转的、右边是待处理的，循环每跑一次就把右边最前面那个节点摘下来接到左边的头上。

p2 初始为 null 不是随便写的：原来的头节点反转后会变成尾节点，尾节点的 next 必须是 null，让第一轮 p1.next = p2 正好赋成 null，一步到位。

题解

var reverseList = function (head) {
  let p1 = head;
  let p2 = null;
  while (p1) {
    const tmp = p1.next;
    p1.next = p2;
    p2 = p1;
    p1 = tmp;
  }
  return p2;
};

循环体里那四行的顺序是死的，改动任何一行的位置都会出错，值得逐行确认一遍：

第一行 const tmp = p1.next 先把后继存起来。这一步必须在前面，因为下一行就要覆盖 p1.next 了。

第二行 p1.next = p2 完成实际的反转，把当前节点接到已反转部分的头上。

第三行 p2 = p1，当前节点成为新的已反转部分的头部。

第四行 p1 = tmp，靠之前保存的引用回到待处理部分继续。

初学时容易写成先挪指针再改 next，那样改的就不是当前节点了。也容易漏掉 tmp 直接写 p1 = p1.next，但此时 p1.next 已经被改成了 p2，指针会往回走，直接死循环。

返回的是 p2 而不是 p1。循环退出时 p1 已经是 null（走过了原链表的尾部），而 p2 停在最后一个被处理的节点上，也就是原链表的尾节点、新链表的头节点。

边界情况都被自然覆盖了：传入空链表时 while 一次都不进，返回 p2 也就是 null；单节点链表跑一轮，next 被设为 null，返回它自己。

时间复杂度：while => O(n)
空间复杂度：O(1)

空间是 O(1)，因为只用了三个指针变量，不随链表长度增长。这一点比递归解法优：递归版写起来更短，但调用栈深度等于链表长度，空间是 O(n)，链表很长时会栈溢出。所以工程上一般选这个迭代版本。