labuladong原始讲解 https://labuladong.online/algo/data-structure-basic/linkedlist-basic/

你好！我是你的OI竞赛教练。今天我们不讲枯燥的语法，而是要攻克 链表（Linked List） 这一数据结构在竞赛中的核心解题套路。

Labuladong 的这篇关于链表的文章非常经典，核心就讲了两个词：双指针（Two Pointers） 和 虚拟头结点（Dummy Node）。

这份课件将这两大思想拆解为 OI 选手必须掌握的 6 个核心模型。

---

OI 专题：链表双指针技巧大全

1. 课前预备知识 (Prerequisites)

在开始前，请确保你习惯以下 OI 风格的链表定义：

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

核心思维：

• 链表题大多不难，难在细节（判空、边界）。
• 空间复杂度 $O(1)$ 是链表题的常见约束，这意味着你不能开数组存节点，必须玩转指针。

---

2. 读题关键词 (Keywords Analysis)

当你看到题目涉及“链表”且包含以下关键词时，请立即联对应的解题模型：

关键词	联想模型/技巧
合并 (Merge)、分解 (Partition)	虚拟头结点 (Dummy Node)
倒数第K个	快慢指针 (固定间距)
中间节点	快慢指针 (速度差 2倍)
是否有环	快慢指针 (追及问题)
环的入口	快慢指针 (数学推导)
公共节点 (Intersection)	指针连接 (拼接路径)

---

3. 模型一：合并与分解 (Merge & Partition)

核心技巧：虚拟头结点 (Dummy Node)

痛点：在合并或构建新链表时，头结点通常需要特判（比如一开始是空的）。注意后面 树 的题目也有可能有多个根root（变成森林），则可以添加一个虚拟根dummy-root变成一棵树。树实际上是链表合并而成的。 解法：创建一个假的 dummy 节点，dummy->next 指向真正的头。

3.1 合并两个有序链表

• 思路：谁小谁先上，穿针引线。
• OI 代码实现：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 技巧：使用虚拟头结点，避免处理空指针
    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;
    ListNode* p1 = l1;
    ListNode* p2 = l2;

    while (p1 != NULL && p2 != NULL) {
        if (p1->val < p2->val) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next; // 指针后移
    }
    
    // 把剩余的接上
    if (p1 != NULL) p->next = p1;
    if (p2 != NULL) p->next = p2;

    return dummy->next;
}

3.2 链表的分解 (Partition List)

• 题目：把小于 $x$ 的放左边，大于等于 $x$ 的放右边，保持相对顺序。
• 启发式图解：想象把原始链表拆成两个小链表 small_list 和 large_list，最后把 small 的尾巴接到 large 的头上。
• 易错点（教练敲黑板）：原链表的节点被拆下来后，一定要把 next 指针断开，否则会形成环！

ListNode* partition(ListNode* head, int x) {
    ListNode* dummy1 = new ListNode(-1); // 存 < x
    ListNode* dummy2 = new ListNode(-1); // 存 >= x
    ListNode* p1 = dummy1;
    ListNode* p2 = dummy2;
    ListNode* p = head;

    while (p != NULL) {
        if (p->val < x) {
            p1->next = p;
            p1 = p1->next;
        } else {
            p2->next = p;
            p2 = p2->next;
        }
        
        // 【关键步骤】断开原链表中的连接，防止成环
        ListNode* temp = p->next;
        p->next = NULL; 
        p = temp;
    }
    
    // 拼接两个链表
    p1->next = dummy2->next;
    return dummy1->next;
}

---

4. 模型二：合并 K 个有序链表

• 思路：是“合并两个”的进阶版。每次从 K 个头中选最小的，怎么选最快？
• 工具：优先队列 (Priority Queue)。
• 复杂度：$O(N \log K)$。

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // 最小堆
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return NULL;
    
    // 优先队列存节点指针
    priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
    
    for (ListNode* node : lists) {
        if (node) pq.push(node);
    }

    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;

    while (!pq.empty()) {
        ListNode* node = pq.top();
        pq.pop();
        
        p->next = node;
        p = p->next;
        
        if (node->next) pq.push(node->next);
    }
    
    return dummy->next;
}

---

5. 模型三：单链表的倒数第 K 个节点

• 启发式思考：只遍历一次，怎么知道谁是倒数第 K 个？
• 尺子法：想象你拿着一把长度为 $K$ 的“尺子”。
  1. 先让 p1 走 $K$ 步。
  2. 然后 p1 和 p2 同时走。
  3. 当 p1 走到尽头（NULL）时，p2 刚好在倒数第 $K$ 个位置。

ListNode* findFromEnd(ListNode* head, int k) {
    ListNode* p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        // OI中通常保证 k 合法，严谨一点可以判空
        if (p1 == NULL) return NULL; 
        p1 = p1->next;
    }
    
    ListNode* p2 = head;
    // p1, p2 同时走
    while (p1 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }
    // 此时 p2 指向倒数第 k 个
    return p2;
}

---

6. 模型四：寻找链表中点

• 痛点：不知道链表长度。
• 快慢指针法：两个人赛跑。
  • slow 一次走 1 步。
  • fast 一次走 2 步。
  • 当 fast 到终点时，slow 刚好在中间。

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

---

7. 模型五：判断回文链表 (综合应用)

• 思路：
  1. 用快慢指针找到中点。
  2. 反转后半部分链表（经典操作）。
  3. 比较前半部分和反转后的后半部分。
  4. (可选) 恢复链表。

---

8. 模型六：环形链表 (Cycle) - 重难点

8.1 判断是否有环

• 原理：操场跑圈。如果 fast 比 slow 快，且有环，fast 最终一定会套圈 slow（相遇）。

bool hasCycle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true; // 相遇即有环
    }
    return false;
}

8.2 寻找环的起点 (数学推导)

草稿纸推演： 假设相遇时，Slow 走了 $k$ 步，Fast 走了 $2k$ 步。 Fast 比 Slow 多走了 $k$ 步，这 $k$ 步一定是环长度的整数倍。 设相遇点距离环起点为 $m$，起点距离环入口为 $x$。 结论：从相遇点再派一个指针从头开始走，二者会在环入口相遇。

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    
    // 1. 先判断是否有环
    bool hasCycle = false;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    if (!hasCycle) return NULL;
    
    // 2. 找环入口：slow留在原地，fast回到起点（或者新建一个ptr）
    // 此时两指针速度调整为一致，一次一步
    fast = head;
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow; // 相遇点即为入口
}

---

9. 模型七：两个链表的交点

• 问题：两个单链表像 "Y" 字形一样相交，找出交点。
• 暴力法：Hash表存一个链表的所有节点，太慢。
• 双指针法（浪漫相遇）：
  • 指针 p1 走完链表 A 后，跳到链表 B 头继续走。
  • 指针 p2 走完链表 B 后，跳到链表 A 头继续走。
  • 原理：$L_A + L_B = L_B + L_A$。他们走过的总路程一样，最终一定会在交点相遇（或者在 NULL 处相遇）。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *p1 = headA;
    ListNode *p2 = headB;
    
    while (p1 != p2) {
        // 如果走到尽头，就转到另一个链表
        // 这里的逻辑巧妙地处理了没有交点的情况（都会变成NULL然后退出）
        p1 = (p1 == NULL) ? headB : p1->next;
        p2 = (p2 == NULL) ? headA : p2->next;
    }
    return p1;
}

---

10. 课后总结 (Summary)

链表题在 OI 中通常不会单独作为一道大题（除非是模拟），但它是很多复杂数据结构（如邻接表、哈希表、键值映射）的基石。

记住这两把钥匙：

1. 虚拟头结点：解决“头都没了怎么办”的问题。
2. 双指针：
   • 快慢指针：解决中点、环、倒数K。
   • 多指针：解决合并、分解、相交。

请大家在草稿纸上默写一遍“寻找环起点”的逻辑图，下课！

---

教练收到了！

根据我们刚才讲解的 链表双指针技巧（寻找中点、反转链表、合并链表、虚拟头结点），最经典的练习题莫过于 “重排链表” (Reorder List)。

这道题是链表基础操作的集大成者。它看起来只需要操作一次，实际上需要你连续运用 “找中点” + “反转” + “合并” 三大模型。能独立写出这道题，说明你的链表基本功已经过关了。

---

习题：链表的“折叠”重排

【题目描述】

给定一个单链表 $L$，其节点顺序为 $L_1 \to L_2 \to L_3 \to \dots \to L_{n-1} \to L_n$。 请你将其重新排列，使得链表变为如下顺序： $L_1 \to L_n \to L_2 \to L_{n-1} \to L_3 \to L_{n-2} \to \dots$

即：将链表的后半部分反转，然后依次插入到前半部分的缝隙中，就像折叠一张纸条一样。

要求：

1. 原地操作：不能申请数组来存储节点值，必须通过修改指针来实现。
2. 时间复杂度：$O(N)$。
3. 空间复杂度：$O(1)$。

【输入格式】

第一行包含一个整数 $N$，表示链表的长度。 第二行包含 $N$ 个整数，表示链表节点依次存储的数值。

【输出格式】

输出重排后的链表节点数值，每个数值之间用空格分隔。

【样例 1】

输入

4
1 2 3 4

输出

1 4 2 3

【样例 2】

输入

5
1 2 3 4 5

输出

1 5 2 4 3

【数据范围】

• $1 \le N \le 50000$
• 节点数值在 int 范围内。

---

【解题思路提示】

这道题不能直接硬做，需要像做外科手术一样分解步骤。请回忆我们课件中的模型：

1. 寻找切分点（模型四）： 目标是将链表一分为二。使用 快慢指针 找到链表的中点 mid。

   • 左半段：$L_1 \dots mid$
   • 右半段：$mid.next \dots L_n$
   • 注意：记得断开两段链表的连接！

2. 反转右半段（模型五的子步骤）： 左半段顺序是对的，但右半段我们需要它倒过来（$L_n \to L_{n-1} \dots$）。 使用标准的 链表反转 算法处理右半段。

3. 合并两链表（模型一）： 现在你有两个链表：

   • List A: $1 \to 2 \to 3$
   • List B: $5 \to 4$ 使用双指针，像拉链一样将 List B 的节点依次插入 List A 的节点之间。

---

【参考代码 (C++14 OI Style)】

#include <bits/stdc++.h>
using namespace std;

// 1. 定义链表节点 (OI 风格)
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    // ------------------------------------------------
    // 步骤 A: 寻找中点 (快慢指针)
    // ------------------------------------------------
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // ------------------------------------------------
    // 步骤 B: 反转链表 (经典三指针)
    // ------------------------------------------------
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next; // 暂存下一步
            curr->next = prev;               // 回头
            prev = curr;                     // 推进 prev
            curr = nextTemp;                 // 推进 curr
        }
        return prev; // prev 变成了新的头
    }

    // ------------------------------------------------
    // 步骤 C: 合并两个链表 (拉链法)
    // l1: 1 -> 2 -> 3
    // l2: 5 -> 4
    // ------------------------------------------------
    void mergeList(ListNode* l1, ListNode* l2) {
        while (l1 != nullptr && l2 != nullptr) {
            ListNode* l1_next = l1->next;
            ListNode* l2_next = l2->next;

            l1->next = l2; // l1 接 l2
            l2->next = l1_next; // l2 接原本 l1 的后面

            l1 = l1_next;
            l2 = l2_next;
        }
    }

    // ------------------------------------------------
    // 主逻辑：折叠重排
    // ------------------------------------------------
    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return;

        // 1. 找中点
        ListNode* mid = findMiddle(head);
        
        // 2. 切断链表，分成左右两半
        ListNode* rightHead = mid->next;
        mid->next = nullptr; 

        // 3. 反转右半部分
        rightHead = reverseList(rightHead);

        // 4. 合并左半部分(head) 和 右半部分(rightHead)
        mergeList(head, rightHead);
    }
};

// ------------------------------------------------
// 辅助函数：构建和打印链表 (用于 IO)
// ------------------------------------------------
ListNode* buildList(int n) {
    if (n == 0) return nullptr;
    int val;
    cin >> val;
    ListNode* head = new ListNode(val);
    ListNode* curr = head;
    for (int i = 1; i < n; i++) {
        cin >> val;
        curr->next = new ListNode(val);
        curr = curr->next;
    }
    return head;
}

void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        cout << curr->val << (curr->next ? " " : "");
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    // 优化 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while (cin >> n) {
        ListNode* head = buildList(n);
        
        Solution sol;
        sol.reorderList(head);
        
        printList(head);
    }
    return 0;
}

【自我检查点】

做完这道题，请问自己三个问题：

1. 寻找中点时，while 循环的条件 fast && fast->next 写对了吗？
2. 切割链表时，有没有记得 mid->next = nullptr？如果不断开，反转和合并时会产生环，导致死循环。
3. 合并链表时，临时变量 l1_next 和 l2_next 保存了吗？如果不保存，指针一旦修改，后面的节点就丢了。