链表操作模板（反转 · 合并 · 删除节点）

反转链表（LeetCode 206）

迭代（工程首选）：

ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

递归：

ListNode reverseListRec(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseListRec(head.next);
    head.next.next = head;  // 让后继节点指向自己
    head.next = null;
    return newHead;
}

反转链表 II（LeetCode 92）：反转 [left, right] 区间的节点，使用哑节点：

ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0, head);
    ListNode pre = dummy;
    for (int i = 1; i < left; i++) pre = pre.next;

    ListNode cur = pre.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy.next;
}

合并两个有序链表（LeetCode 21）

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

合并 K 个有序链表（LeetCode 23）：

1. 优先队列（最小堆）：O(N log k)
2. 分治合并：O(N log k)

// 最小堆方案
ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode l : lists) if (l != null) pq.offer(l);
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        cur.next = pq.poll();
        cur = cur.next;
        if (cur.next != null) pq.offer(cur.next);
    }
    return dummy.next;
}

删除链表的倒数第 N 个节点（LeetCode 19）

快慢指针：快指针先走 N 步，然后同步，快到末尾时慢指针恰好在目标节点前一个：

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;  // 多走1步，slow停在目标前
    while (fast != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
}

删除排序链表中的重复元素

保留一个（LeetCode 83）：

ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    while (cur != null && cur.next != null) {
        if (cur.val == cur.next.val) cur.next = cur.next.next;
        else cur = cur.next;
    }
    return head;
}

全部删除（LeetCode 82）：用哑节点，发现重复就跳过整段：

ListNode deleteDuplicatesAll(ListNode head) {
    ListNode dummy = new ListNode(0, head), pre = dummy;
    while (pre.next != null) {
        ListNode cur = pre.next;
        if (cur.next != null && cur.val == cur.next.val) {
            int val = cur.val;
            while (pre.next != null && pre.next.val == val) pre.next = pre.next.next;
        } else {
            pre = pre.next;
        }
    }
    return dummy.next;
}