怎样反转链表、判断链表有环？

简答

链表是一串节点，每个节点存一个值和一个指向下一个节点的 next。它和数组不同，不能按下标直接访问第几个，只能从头一个个往后走；可是在已知节点后面插入或删除，只要改指针，不用像数组那样挪动后面的元素。

反转链表就是让每个节点的 next 改为指向它前面的节点。遍历时用三个变量：prev 是已经反转好的部分的头，current 是当前节点，next 先把下一个节点记下来，免得改了指针以后找不到后面的节点。每一步把 current.next 指向 prev，然后三个指针一起往后挪。走完以后 prev 就是新的头。

判断有没有环用快慢指针。两个指针都从头出发，慢的每次走一步，快的每次走两步。没有环时快指针会先走到 null；有环时两个指针最终都会进入环里一直转，快指针每轮比慢指针多走一步，迟早追上，所以两者相遇就说明有环。

要注意，用一个 Set 记录走过的节点也能判断有环，写法更直观，但要 O(n) 的额外空间，面试中常被追问能不能做到 O(1)，答案就是快慢指针。

代码实现

先用数组构造一个链表，再反转并检查有没有环：

function fromArray(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = { value: values[i], next: head };
  }
  return head;
}

function toArray(head) {
  const values = [];
  for (let node = head; node; node = node.next) values.push(node.value);
  return values;
}

function reverse(head) {
  let prev = null;
  let current = head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

const list = fromArray([1, 2, 3, 4]);
console.log(toArray(reverse(list)).join()); // 4,3,2,1

const cyclic = fromArray([1, 2, 3]);
cyclic.next.next.next = cyclic.next; // 3 指回 2，形成环
console.log(hasCycle(cyclic)); // true
console.log(hasCycle(fromArray([1, 2, 3]))); // false
console.log(reverse(null)); // null

reverse 里为什么要先存 next？因为下一行 current.next = prev 会把指向后面的指针改掉，如果没提前存起来，就再也找不到后面的节点，链表就断了。

hasCycle 的循环条件为什么是 fast && fast.next？快指针一次要走两步，必须保证它和它的下一个都存在，否则 fast.next.next 会读 null 的属性而报错。空链表和只有一个节点的链表也被这个条件直接处理了，返回 false。

前端哪里会用到链表

React 的 Fiber 节点就用 child、sibling、return 指针连起来，遍历组件树时不用递归，见《React 的虚拟 DOM 和 diff 是怎样工作的？Fiber 解决了什么问题？》。LRU 缓存的经典实现是哈希表加双向链表，JS 里用 Map 的插入顺序可以代替，见《如何利用 Map 实现固定容量的 LRU 缓存？》。

常见追问

怎样找到环的入口？

快慢指针相遇后，把其中一个放回链表头，然后两个指针都改成每次走一步，再次相遇的节点就是环的入口。原因是从头到入口的距离，等于从相遇点继续走到入口的距离加上若干整圈。

怎样找链表的中间节点？

同样用快慢指针，快指针走两步、慢指针走一步，快指针走到末尾时，慢指针正好在中间。

递归能反转链表吗？

能。先递归反转 head.next 之后的部分，再让 head.next.next = head、head.next = null。写法短，但链表很长时递归层数太多可能栈溢出，循环写法更稳妥。