链表（4 题）

LeetCode 预定义结构（JS 版）：

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

链表三大技巧：哑结点（dummy）、双指针、画图。写之前先在纸上画 3 个节点。 返回目录：4.algorithms/题单.md

1. 反转链表

题意：反转整个单链表。 思路：三指针迭代。先存 next，再改指向，最后推进。 复杂度：时间 O(n)，空间 O(1)。 易错：顺序不能反——先改 head.next 就找不到后面的节点了。 追问：「递归怎么写？」——newHead = reverseList(head.next)，再让 head.next.next = head、head.next = null，空间 O(n)。

function reverseList(head) {
  let prev = null;
  while (head) {
    const next = head.next; // 1. 先存
    head.next = prev; // 2. 改指向
    prev = head; // 3. 推进
    head = next;
  }
  return prev;
}

2. 合并两个有序链表

题意：把两个升序链表合并成一个升序链表。 思路：哑结点 + 尾指针，谁小接谁。 复杂度：时间 O(m + n)，空间 O(1)。 易错：循环结束后剩下的那一截直接整体接上，不用再逐个搬。 追问：「合并 K 个怎么做？」——两两合并（分治）或最小堆，O(N log k)。

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode();
  let tail = dummy;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 || list2; // 剩下的直接接上
  return dummy.next;
}

3. 环形链表

题意：判断链表里有没有环。 思路：快慢指针，快指针每次走两步，有环必相遇。 复杂度：时间 O(n)，空间 O(1)。 易错：循环条件是 fast && fast.next，两个都要判，否则空指针。 追问：「环的入口在哪？」——相遇后把一个指针放回头部，两个同速走，再次相遇就是入口（Floyd 判圈）。

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;
}

4. K 个一组翻转链表

题意：每 k 个节点一组翻转，不足 k 个保持原样。 思路：哑结点 + 每组先找到第 k 个节点，然后组内反转并接回去。 复杂度：时间 O(n)，空间 O(1)。 易错：三处指针都要接对——groupPrev.next = kth、组尾接 groupNext、然后 groupPrev 移到原组头。 易错：反转时用 prev = groupNext 起手，天然把组尾接到下一组，不用单独处理。

function reverseKGroup(head, k) {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;

  while (true) {
    let kth = groupPrev; // 找本组第 k 个节点
    for (let i = 0; i < k && kth; i++) kth = kth.next;
    if (!kth) break; // 不足 k 个，结束

    const groupNext = kth.next;
    let prev = groupNext; // 组尾最终指向下一组的头
    let cur = groupPrev.next;
    while (cur !== groupNext) {
      const next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }

    const groupHead = groupPrev.next; // 反转前的组头，反转后变成组尾
    groupPrev.next = kth; // 接上新组头
    groupPrev = groupHead; // 移到下一组的前驱
  }

  return dummy.next;
}