链表技巧

链表概览

链表是每个节点持有数据与下一节点指针的线性结构。与数组相比，插入/删除 O(1)，随机访问 O(n)。C++ 面试中通常用结构体手写节点，或用 std::list（双向链表）。

节点定义

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v, ListNode* n = nullptr) : val(v), next(n) {}
};

基本操作复杂度

核心技巧速览

• 快慢指针：检测环、找中点、找环入口
• 翻转：原地翻转整条或一段链表
• 合并：归并排序式有序链表合并
• 哨兵（dummy head）：统一头部边界，简化代码
• 倒数第 N 个：快指针先走 N 步，双指针同步

快慢指针

慢指针每次走 1 步，快指针每次走 2 步。二者速度差产生两个经典应用：

使用场景

• 找链表中点：快指针到达末尾时，慢指针恰好在中间
• Floyd 判环：若链表有环，快慢指针必然在环内相遇
• 找环入口（142）：相遇后将一个指针移回 head，两指针同速走，再次相遇即为环入口

// Find the middle node of a linked list (fast & slow pointers)
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  // right-center for even-length lists
}

// Floyd's cycle detection
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // they met inside the cycle
    }
    return false;
}

边界提示：找中点时，奇数长度 slow 停在正中；偶数长度 slow 停在「中右」节点。若需「中左」，循环条件改为 fast->next && fast->next->next。

链表翻转

三指针迭代法：prev、curr、next。每次将 curr->next 指向 prev，然后三者前进一步。也可用递归，但空间 O(n)。

常见变体

• 翻转整条链表（206）
• 翻转 [left, right] 区间（92）——先走到 left-1，再翻转 right-left+1 个节点
• K 个一组翻转（25）——反复找长度 K 的段，逐段翻转

// Iterative reversal — O(n) time, O(1) space
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;  // save next
        curr->next = prev;            // redirect
        prev = curr;                  // advance prev
        curr = next;                  // advance curr
    }
    return prev;  // new head
}

// Reverse segment [left, right] (1-indexed)
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(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* nxt = cur->next;
        cur->next = nxt->next;
        nxt->next = pre->next;
        pre->next = nxt;
    }
    return dummy.next;
}

易错点：翻转后原 head 变成 tail，要提前保存或用哨兵节点拼接前后段。

合并有序链表

归并两个已排序链表：设 dummy 节点作起点，比较两个链表的当前节点，将较小的接入 dummy 链，指针前进，最后把非空链接在末尾。

应用

• 合并两条有序链表（21）
• 合并 K 条有序链表（23）——用最小堆或分治
• 链表归并排序（148）——递归拆分 + 合并两条

// Merge two sorted linked lists — O(m+n) time, O(1) space
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* 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 ? l1 : l2;  // attach remaining
    return dummy.next;
}

时间复杂度：合并两条长度 m、n 的链表：O(m + n)，空间 O(1)（原地拼接指针）。

哨兵节点 & 倒数第 N 个

哨兵（dummy）节点是值无意义的额外头节点，让「在 head 前插入」和「删除 head」与普通节点操作一致，无需特判。

倒数第 N 个节点

1. 快指针先走 N 步
2. 快慢指针同步走，直到快指针到达末尾
3. 此时慢指针的下一个即为待删节点
4. slow->next = slow->next->next 完成删除

// Remove Nth node from end — one pass with dummy + two pointers
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;
    for (int i = 0; i <= n; i++) fast = fast->next;  // fast leads by n+1
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    // slow is now the node BEFORE the target
    ListNode* del = slow->next;
    slow->next = del->next;
    delete del;
    return dummy.next;
}

与哨兵配合：将 dummy 作为 slow 的起点，可直接处理删除 head 的边界情况，无需额外判断。