对应题目

序号	题号	题目名称	练什么	说明
1	206	反转链表	链表指针操作	最基础最高频，必须秒做。练习用三个指针（prev/curr/next）逐个翻转节点
2	21	合并两个有序链表	链表遍历和比较	练习同时遍历两个链表，比较后串联。可以用虚拟头节点简化代码
3	141	环形链表	快慢指针	经典的快慢指针判断链表是否有环，快指针走两步慢指针走一步
4	142	环形链表 II	快慢指针进阶	不仅判断有没有环，还要找到环的入口。需要理解数学推导
5	160	相交链表	双指针	找两个链表的交点。两个指针分别走完自己的再走对方的，会在交点相遇
6	19	删除链表的倒数第N个节点	快慢指针	快指针先走N步，然后快慢一起走，慢指针到达要删除的位置
7	24	两两交换链表中的节点	链表指针操作	练习复杂一点的指针交换操作，画图理解
8	25	K个一组翻转链表	链表综合	较难，206的升级版，练习分组处理链表。做不出来可以先跳过

C语言基础 + 链表结构与基本操作

一、指针

核心概念

• 指针变量存的是另一个变量的内存地址
• &取地址，*解引用（通过地址取值）

1. 指针核心概念

• 指针变量存的是另一个变量的内存地址
• & 取地址，* 解引用（通过地址取值）
• * 在声明时表示"这是指针"，在使用时表示"取出指向的值"

int a = 10;
int *p = &a;    // p存的是a的地址
*p = 20;        // 通过p修改a的值，a变成20

• NULL：指针不指向任何有效地址时赋值为NULL。链表末尾节点的next就是NULL
• 解引用NULL指针会导致程序崩溃，使用指针前要检查是否为NULL

2. 指针作为函数参数

C语言函数传参是值传递（传副本）。要在函数内部修改外部变量，必须传该变量的地址：

void change(int *p) { *p = 100; }   // 通过指针修改外部变量
int a = 10;
change(&a);    // a变成100

推广规则：想在函数内部修改什么，就传那个东西的地址。

• 修改int → 传 int *
• 修改 struct ListNode *（即head指针）→ 传 struct ListNode **

3. 结构体

• 把多个不同类型的变量打包成一个整体
• 通过变量访问成员用 .，通过指针访问成员用 ->
• 链表里几乎全用 -> ，因为操作的都是指向节点的指针

struct Student stu;
struct Student *p = &stu;
stu.age = 22;     // 变量用.
p->age = 22;      // 指针用->（等价于 (*p).age）

• 结构体里可以放指向自身类型的指针 → 这就是链表节点的核心

4. typedef

给类型起别名，简化写法：

typedef struct Node {
    int val;
    struct Node *next;   // 内部必须用 struct Node，因为typedef还没生效
} Node;
// 之后可以直接写 Node *p; 代替 struct Node *p;

LeetCode上题目给的定义用的是 struct ListNode，不用typedef，直接用就行。

---

二、动态内存分配

1. 栈 vs 堆

	栈（Stack）	堆（Heap）
分配方式	自动（声明局部变量时）	手动（malloc）
释放方式	自动（函数返回时）	手动（free）
生命周期	与函数绑定	由程序员控制
大小	较小	较大

链表节点必须在堆上创建：节点数量动态变化，且不能和某个函数的生命周期绑定。

2. malloc

什么时候只需要定义链表节点指针，什么时候需要malloc分配链表节点内存？关键在于是否需要创建新节点，如果只是已经有的节点改指向之类的，没有需要多创建别的节点，那就只需要定义链表节点指针来操作就可以。 如果除了题目已经有的节点还需要有新的节点，那么就需要malloc分配新的链表节点内存。

malloc创建新节点以后别忘了给新节点初始化

#include <stdlib.h>
void *malloc(size_t size);   // 申请size字节的堆内存，返回起始地址

• 返回 void *（通用指针），赋值给具体类型时加强制类型转换
• 申请失败返回NULL
• malloc后的内存未初始化，必须手动赋值

struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->val = 10;
node->next = NULL;    // 必须手动设置

3. free

什么时候需要free？

malloc了新节点不过这个节点没有加在结果链表里（比如虚拟头节点，一般用虚拟头节点都是要返回虚拟头节点的next，所以free虚拟头节点前别忘了保存一下虚拟头节点的next）或者删除不需要的节点（用指针保存一下目标节点再free）

void free(void *ptr);   // 释放malloc申请的内存

• 传入的必须是malloc返回的地址
• free后将指针设为NULL（防止野指针）
• 不free → 内存泄漏（LeetCode刷题不严格要求，但面试时提一嘴加分）

4. LeetCode中的实际情况

• 不需要检查malloc是否失败
• 不需要free（不影响通过，但知道概念）
• 创建节点的标准写法：

struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->val = 某个值;
node->next = NULL;

---

三、链表的结构

节点定义（LeetCode统一格式）

struct ListNode {
    int val;                 // 数据
    struct ListNode *next;   // 指向下一个节点，末尾为NULL
};

链表 与 数组

• 数组：内存连续，可通过下标O(1)访问任意位置，但插入删除需移动元素O(n)
• 链表：内存不连续靠next串联，只能从头遍历O(n)，但插入删除只改指针O(1)

头指针 head

• 指向第一个节点的指针，通过它访问整个链表
• 空链表：head = NULL
• 遍历时不要移动head，创建临时指针cur来遍历

---

四、链表基本操作

核心原则

修改指针之前，确保不会丢失任何节点的引用。一个节点如果没有任何指针指向它，就断链丢失了。

---

1. 遍历

思路：用临时指针cur从head出发，每次移动到next，直到NULL。

struct ListNode *cur = head;
while (cur != NULL) {
    // 处理 cur->val
    cur = cur->next;
}

---

2. 创建节点

思路：malloc申请内存 → 设置val → 设置next为NULL → 返回指针。

struct ListNode *createNode(int val) {
    struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

---

3.插入

（1）头插（在链表最前面插入）— O(1)

思路：

1. 新节点的next指向原来的头节点
2. head更新为新节点

newNode->next = head;
head = newNode;

• 空链表也适用（第一步相当于 newNode->next = NULL）
• 构建的链表顺序与插入顺序相反

---

（2）尾插（在链表最后面插入）— O(n)

思路：

1. 特殊情况：空链表 → 直接让head指向新节点，返回
2. 找到最后一个节点（next为NULL的那个）
3. 最后一个节点的next指向新节点

if (head == NULL) { head = newNode; return; }

struct ListNode *cur = head;
while (cur->next != NULL) {   // 停在最后一个节点上，所以检查cur->next
    cur = cur->next;
}
cur->next = newNode;

• while条件是 cur->next != NULL：因为需要停在最后一个节点上来修改它的next。如果写 cur != NULL，循环结束时cur已经是NULL，没法操作了
• 构建的链表顺序与插入顺序一致

---

（3）在指定节点后插入 — O(1)

思路（两步，顺序不能反）：

1. 先接后面：新节点的next指向prev原来的下一个节点
2. 再接前面：prev的next指向新节点

newNode->next = prev->next;   // 第一步：必须先做
prev->next = newNode;         // 第二步

• 为什么不能反：如果先做第二步，prev->next被覆盖成newNode，原来prev后面的节点地址就丢了，断链

---

4. 删除

（1）删除头节点

思路：

1. 保存头节点（用于释放）
2. head移动到下一个节点
3. 释放原头节点

struct ListNode *temp = head;
head = head->next;
free(temp);

---

（2） 删除指定值的节点

思路：分两种情况。

情况一：要删除的是头节点 → 按"删除头节点"处理

情况二：一般情况：

1. 找到目标节点的前一个节点prev（通过检查 prev->next->val 是否等于目标值）
2. 保存目标节点 temp = prev->next
3. prev的next跳过目标节点：prev->next = temp->next
4. 释放目标节点 free(temp)

// 情况一
if (head->val == val) { temp = head; head = head->next; free(temp); return; }

// 情况二
struct ListNode *prev = head;
while (prev->next != NULL && prev->next->val != val) {
    prev = prev->next;
}
if (prev->next != NULL) {
    struct ListNode *temp = prev->next;
    prev->next = temp->next;
    free(temp);
}

• 痛点：头节点没有prev，必须单独处理 → 用虚拟头节点解决（见下篇）

---

5. 释放整个链表

思路：遍历每个节点，先保存当前节点，移动到下个节点，再free当前节点。（free后不能再访问 cur->next，所以必须先保存）

while (cur != NULL) {
    struct ListNode *temp = cur;
    cur = cur->next;    // 先移动
    free(temp);         // 再释放
}

---

6. 查找 & 求长度

• 按值查找：从head遍历，逐个比较val，找到返回节点指针，没找到返回NULL
• 求长度：从head遍历，计数器++，直到NULL

LeetCode 链表题常用技巧

一、虚拟头节点（Dummy Head）

解决什么问题

很多链表操作中，头节点需要特殊处理（因为头节点没有prev），导致代码要分两种情况写。虚拟头节点就是在真正的第一个节点前面人为加一个额外节点，让所有真实节点（包括原头节点）都有prev，从而统一处理逻辑。

没有dummy：head → [1] → [2] → [3] → NULL     （[1]没有prev，需特殊处理）
有dummy：  dummy → [1] → [2] → [3] → NULL     （[1]的prev是dummy，统一处理）

dummy的val是什么无所谓（一般写0），它不是链表的真正数据，只是辅助工具。

什么时候用

操作过程中头节点可能被修改（被删除、被替换、新节点插到头部前面）时，就用虚拟头节点。

计划中会用到的题目：21（合并有序链表）、19（删除倒数第N个）、24（两两交换）、25（K个一组翻转）。

使用思路

1. 创建dummy节点，让 dummy->next = head
2. 从dummy开始操作（此时所有真实节点都可以用统一逻辑处理）
3. 返回 dummy->next（不是返回head！因为操作后原来的head可能已经不是第一个节点了，但dummy->next永远指向操作后的真正第一个节点）

struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = head;

// ... 各种操作，从dummy开始 ...

struct ListNode *result = dummy->next;   // 真正的头
free(dummy);
return result;

示例：用dummy重写"删除指定值的节点"

不需要分情况了，对比上篇笔记中需要单独处理头节点的版本：

思路：

1. 创建dummy，dummy->next = head
2. prev从dummy开始遍历（这样原头节点也被当作"prev的下一个"来统一处理）
3. 如果prev->next的值等于目标值 → 删除prev->next
4. 否则prev前进
5. 返回dummy->next

struct ListNode* deleteByValue(struct ListNode* head, int val) {
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;

    struct ListNode *prev = dummy;       // 从dummy开始，不是从head开始
    while (prev->next != NULL) {
        if (prev->next->val == val) {
            struct ListNode *temp = prev->next;
            prev->next = temp->next;
            free(temp);
            break;
        }
        prev = prev->next;
    }

    struct ListNode *result = dummy->next;
    free(dummy);
    return result;
}

原来的头节点现在是dummy->next，和其他节点一样都有prev（就是dummy），所以一个while循环就处理了所有情况。

---

二、三指针反转法

解决什么问题

反转链表：把 1 → 2 → 3 → NULL 变成 3 → 2 → 1 → NULL。这是题目206，也是很多其他链表题的基础操作。

核心思路

遍历链表，逐个把每个节点的next从"指向后一个"改成"指向前一个"。需要三个指针：

• prev：当前节点反转后应该指向的目标（即它前面的节点）
• cur：当前正在处理的节点
• next：提前保存cur的下一个节点（因为马上要把cur->next改掉，改掉后就找不到下一个了）

操作步骤（每轮循环做四件事）

1. 保存：next = cur->next（保存下一个，防止断链）
2. 反转：cur->next = prev（当前节点的next指向前面）
3. prev前进：prev = cur
4. cur前进：cur = next

循环结束条件：cur == NULL（所有节点处理完了）。结束时prev指向的就是新的头节点。

逐步过程

初始：prev=NULL, cur=节点1

第一轮（处理节点1）：
  保存：next = 节点2
  反转：节点1->next = NULL (prev)
  前进：prev = 节点1, cur = 节点2
  状态：NULL ← [1]   [2] → [3] → NULL
                ↑      ↑
               prev   cur

第二轮（处理节点2）：
  保存：next = 节点3
  反转：节点2->next = 节点1 (prev)
  前进：prev = 节点2, cur = 节点3
  状态：NULL ← [1] ← [2]   [3] → NULL
                       ↑     ↑
                      prev  cur

第三轮（处理节点3）：
  保存：next = NULL
  反转：节点3->next = 节点2 (prev)
  前进：prev = 节点3, cur = NULL
  状态：NULL ← [1] ← [2] ← [3]
                             ↑
                            prev    cur=NULL，循环结束

代码

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *cur = head;

    while (cur != NULL) {
        struct ListNode *next = cur->next;   // 1. 保存
        cur->next = prev;                    // 2. 反转
        prev = cur;                          // 3. prev前进
        cur = next;                          // 4. cur前进
    }

    return prev;   // prev就是新头
}

关键点

• 初始时prev = NULL：因为原来的头节点反转后变成尾节点，尾节点的next应该是NULL
• 四步顺序不能乱：必须先保存next，才能安全地修改cur->next
• 返回prev不是返回head：head还指着原来的节点1（现在是尾节点了），prev才指向新头

---

三、快慢指针

两个指针从head同时出发，慢指针每次走一步，快指针每次走两步。

struct ListNode *slow = head;
struct ListNode *fast = head;
while (条件) {
    slow = slow->next;
    fast = fast->next->next;
}

快慢指针有三个经典用途：

---

用途一：判断链表是否有环（题目141）

什么是环：某个节点的next指向链表中前面的某个节点，遍历会无限循环。

[1] → [2] → [3] → [4]
        ↑               |
        └───────────┘    [4]的next指向[2]

思路：

1. slow和fast都从head出发
2. slow每次走一步，fast每次走两步
3. 如果有环：fast先入环，slow后入环，fast每轮比slow多走一步，距离不断缩小，最终一定会相遇 → 返回true
4. 如果没环：fast先到达NULL → 返回false

循环条件：fast != NULL && fast->next != NULL（因为fast走两步，要保证fast和fast->next都不是NULL，否则解引用会崩溃）

bool hasCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;    // 相遇，有环
    }
    return false;   // fast到了NULL，没环
}

---

用途二：找环的入口（题目142）

不只判断有没有环，还要找到环的入口节点。

前置推导：

head ──a个节点──> 入口 ──b个节点──> 相遇点
                    ↑                     |
                    └────c个节点───────┘
环长 = b + c

相遇时慢指针走了 a+b 步，快指针走了 a+b+n(b+c) 步（n是快指针多转的圈数）。因为快指针速度是慢指针2倍：

2(a+b) = a+b+n(b+c)
化简得：a = (n-1)(b+c) + c

这意味着：从head走a步 和 从相遇点走c步（加若干整圈），会同时到达环入口。

思路：

1. 第一阶段：快慢指针找到相遇点（和判环一样）
2. 第二阶段：一个指针从head出发，一个从相遇点出发，都每次走一步，再次相遇的地方就是环入口

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head, *fast = head;

    // 第一阶段：找相遇点
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // 第二阶段：找环入口
            struct ListNode *p1 = head;     // 从头出发
            struct ListNode *p2 = slow;      // 从相遇点出发
            while (p1 != p2) {
                p1 = p1->next;
                p2 = p2->next;
            }
            return p1;   // 相遇处就是环入口
        }
    }
    return NULL;   // 没有环
}

面试时可能会问推导过程，记住核心等式 a = (n-1)(b+c) + c 以及它的含义就行。

---

用途三：找链表中间节点

思路：fast走两步，slow走一步。fast到末尾时，slow恰好在中间。

• 奇数个节点（如5个）：fast停在最后一个节点时，slow在正中间（第3个）
• 偶数个节点（如4个）：fast走到NULL时，slow在中间偏右（第3个）

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

这个操作本身不是计划里的独立题目，但作为其他题目的子步骤会用到。

---

四、间距双指针

解决什么问题

链表不能从后往前数，也不能直接通过下标访问。间距双指针可以用来找倒数第N个节点（题目19的核心）。

思路

让两个指针之间保持固定间距N，当前面的指针到末尾时，后面的指针就恰好在倒数第N个位置。

操作步骤：

1. fast从head出发，先走N步
2. 然后slow和fast一起走，每次都走一步（保持间距不变）
3. 当fast到达末尾时，slow就在倒数第N个位置

过程示例

链表 [1] → [2] → [3] → [4] → [5] → NULL，找倒数第2个（即节点4）：

第一步：fast先走2步
[1] → [2] → [3] → [4] → [5] → NULL
 ↑           ↑
slow        fast     间距=2

第二步：一起走
[1] → [2] → [3] → [4] → [5] → NULL
        ↑           ↑
       slow        fast

继续一起走：
[1] → [2] → [3] → [4] → [5] → NULL
              ↑           ↑
             slow        fast

继续一起走：
[1] → [2] → [3] → [4] → [5] → NULL
                    ↑           ↑
                   slow        fast

fast->next == NULL，停下。slow在[4]，就是倒数第2个。

在题目19中的应用

题目19是"删除倒数第N个节点"，找到之后还要删除。删除需要知道被删节点的前一个节点，有两种处理方式：

方式一：让fast先走n+1步，这样slow会停在倒数第n+1个（即要删除节点的前一个），然后直接 slow->next = slow->next->next 完成删除。

方式二：配合虚拟头节点。让slow从dummy开始而不是head开始，fast从head先走n步，然后一起走。最终slow会停在要删除节点的前一个。

第二种方式更安全，因为如果要删除的恰好是头节点，dummy能统一处理。