链表

一、链表基础

链表节点定义

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

1. 获取链表长度

function getLength(head: ListNode | null): number {
  let len = 0;
  let cur = head;
  while (cur) {
    len++;
    cur = cur.next;
  }
  return len;
}

2. 插入节点

在 prev 节点之后插入 node：

function insertAfter(prev: ListNode | null, node: ListNode | null): void {
  if (!prev || !node) return;
  node.next = prev.next;
  prev.next = node;
}

3. 删除节点

删除 prev.next：

function deleteAfter(prev: ListNode | null): void {
  if (!prev || !prev.next) return;
  prev.next = prev.next.next;
}

核心思想：链表的删除/插入都要找到「前一个节点」，掌握这一点就掌握了一大半。

二、链表解题模板

1. 虚拟头节点 dummy

使用场景：当头节点可能被删除 / 反转 / 头节点可能发生改变时，使用 dummy 可以避免对头节点的特殊判断。

function withDummy(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0, head);
  let cur = dummy;

  // ... 操作逻辑，统一处理
  while (cur.next) {
    // 通过 cur 操作 cur.next
    cur = cur.next;
  }

  return dummy.next;
}

2. 快慢指针（只记「找前一个节点」的版本）

通过 slow.next 即可获取到目标节点，所以统一记前驱模板。

(1) 寻找中点的前一个节点

当 fast 到达末尾时，slow 位于中点的前一个。适用场景：偶数长度时让 slow 停在前半段最后一个节点（便于断链）。

function findMidPrev(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0, head);
  let slow = dummy;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  return slow; // slow.next 即为中点
}

(2) 寻找倒数第 K 个节点的前一个节点

fast 先走 k 步，然后 slow/fast 同步走，fast 到末尾时 slow.next 即为倒数第 k 个。

function findKthFromEndPrev(head: ListNode | null, k: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let slow = dummy;
  let fast: ListNode | null = head;
  for (let i = 0; i < k && fast; i++) {
    fast = fast.next;
  }
  while (fast) {
    slow = slow.next!;
    fast = fast.next;
  }
  return slow; // slow.next 即为倒数第 k 个
}

3. 判断是否有环

function hasCycle(head: ListNode | null): boolean {
  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. 链表反转

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur: ListNode | null = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

5. 递归模板（O(n) 删除当前节点）

当需要「删除当前节点」时，链表本身没有 prev 指针，最自然的写法是递归返回处理后的链表头。

function deleteCurNode(head: ListNode | null): ListNode | null {
  if (!head) return null;

  head.next = deleteCurNode(head.next);

  // if (shouldDelete(head)) return head.next;  // 删除当前节点
  return head;
}

6. 归并排序

function sortList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;

  // 1. 找中点并断开
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  const mid = slow.next;
  slow.next = null;

  // 2. 递归排序左右
  const left = sortList(head);
  const right = sortList(mid);

  // 3. 合并两个有序链表
  return mergeTwoLists(left, right);
}

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 ?? l2;
  return dummy.next;
}