1. 链表知识点总结 & 例题讲解

一、链表基本概念

1. 定义
- 链表是由节点组成的线性数据结构
- 每个节点包含数据域和指针域
- 通过指针连接各个节点

2. 节点结构

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

3. 链表类型
- 单链表：每个节点只有一个指向下一节点的指针
- 双链表：每个节点有指向前后节点的两个指针
- 循环链表：尾节点指向头节点
- 静态链表：用数组实现的链表

二、链表基本操作

1. 创建链表

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);

2. 遍历链表

ListNode* curr = head;
while (curr != nullptr) {
    // 处理 curr->val
    curr = curr->next;
}

3. 插入节点
- 头部插入：O(1)
- 尾部插入：O(n)
- 中间插入：O(n)

4. 删除节点
- 删除头节点
- 删除中间节点
- 删除尾节点

三、重要技巧

1. 虚拟头节点（Dummy Node）
- 简化边界条件处理
- 统一操作逻辑

ListNode* dummy = new ListNode(0);
dummy->next = head;

2. 双指针技术
- 快慢指针：找中点、检测环
- 前后指针：删除倒数第N个节点
- 左右指针：判断回文

3. 递归思想
- 很多链表问题可以用递归解决
- 注意递归深度和栈溢出

四、经典问题分类

1. 反转问题
- 反转整个链表
- 反转部分链表
- K个一组反转

2. 合并问题
- 合并两个有序链表
- 合并K个有序链表

3. 环形链表
- 判断是否有环
- 找环的入口
- 计算环的长度

4. 删除问题
- 删除特定值的节点
- 删除倒数第N个节点
- 删除重复节点

5. 其他经典题
- 两两交换节点
- 链表相交
- 复制带随机指针的链表
- 链表排序

五、时间复杂度分析

六、空间复杂度

• 链表本身：O(n)
• 额外指针空间：每个节点一个指针
• 递归解法：O(n) 栈空间
• 迭代解法：O(1) 额外空间

七、链表 vs 数组

链表优势：
- 动态大小
- 插入删除效率高（已知位置）
- 内存利用灵活

数组优势：
- 随机访问 O(1)
- 内存连续，缓存友好
- 空间效率高（无需指针）

八、常见陷阱

1. 空指针处理
2. 始终检查 nullptr

3. 注意边界条件

4. 内存泄漏

5. 删除节点时释放内存

6. 使用智能指针

7. 指针丢失

8. 修改指针前保存必要的引用

9. 画图辅助理解

10. 循环条件

11. 注意 curr vs curr->next
12. 避免访问空指针的成员

九、解题模板

// 1. 处理边界条件
if (!head) return nullptr;

// 2. 创建dummy节点（如需要）
ListNode* dummy = new ListNode(0);
dummy->next = head;

// 3. 初始化指针
ListNode* prev = dummy;
ListNode* curr = head;

// 4. 主要逻辑
while (curr) {
    // 处理当前节点
    // 移动指针
}

// 5. 返回结果
return dummy->next;

十、调试技巧

1. 打印链表

void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

1. 画图理解
2. 画出每一步的状态

3. 标注指针指向

4. 分步执行

5. 每次只改变一个指针
6. 验证每步的正确性

2. 例题 Leetcode 24. 两两交换链表中的节点

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        for(auto p = dummy ; p -> next && p -> next -> next ;)
        {
            auto a = p -> next, b = a -> next;
            p -> next = b;
            a -> next = b -> next;
            b -> next = a;
            p = a;
        }
        return dummy -> next;
    }
};

代码逐行分析

函数签名

ListNode* swapPairs(ListNode* head) {

• 输入：链表头指针 head
• 输出：交换后的新链表头指针
• 任务：两两交换相邻节点

创建虚拟头节点

auto dummy = new ListNode(-1);
dummy -> next = head;

• 第1行：创建虚拟头节点，值为-1（任意值）
• 第2行：将虚拟头节点指向原链表头
• 作用：统一处理，避免特殊处理头节点交换的情况

图示：

dummy(-1) -> 1 -> 2 -> 3 -> 4 -> NULL

循环设置

for(auto p = dummy ; p -> next && p -> next -> next ;)

• 初始化：p = dummy，p指向虚拟头节点
• 循环条件：p->next && p->next->next
• p->next 存在：确保p后面至少有一个节点
• p->next->next 存在：确保p后面至少有两个节点
• 含义：只有当p后面有至少两个节点时才进行交换
• 循环更新：在循环体内手动更新

循环体内部 - 保存节点引用

auto a = p -> next, b = a -> next;

• a = p->next：a指向待交换的第一个节点
• b = a->next：b指向待交换的第二个节点

状态图示：

p -> a -> b -> ...
↓    ↓    ↓
dummy -> 1 -> 2 -> 3 -> 4 -> NULL

重新连接指针（核心操作）

p -> next = b;
a -> next = b -> next;
b -> next = a;

逐步分析：

1. p -> next = b;
p -----> b dummy 2 -> 3 -> 4 (跳过了节点1)

2. a -> next = b -> next;
a -----> 3 1 (节点1现在指向3)

3. b -> next = a;
b -> a 2 -> 1 -> 3 -> 4

最终状态：

p -> b -> a -> ...
↓    ↓    ↓
dummy -> 2 -> 1 -> 3 -> 4 -> NULL

移动指针

p = a;

• 将p移动到a的位置（现在a是交换后的第二个节点）
• 为下一轮交换做准备

移动后状态：

         p
         ↓
dummy -> 2 -> 1 -> 3 -> 4 -> NULL

返回结果

return dummy -> next;

• 返回虚拟头节点的下一个节点
• 这是交换后的新链表头

执行过程示例

初始链表：[1,2,3,4]

第一轮循环：

初始: dummy -> 1 -> 2 -> 3 -> 4
     p

执行后: dummy -> 2 -> 1 -> 3 -> 4
              p

第二轮循环：

初始: dummy -> 2 -> 1 -> 3 -> 4
                    p

执行后: dummy -> 2 -> 1 -> 4 -> 3
                         p

循环结束：
- p->next = 3 (存在)
- p->next->next = NULL (不存在)
- 条件不满足，退出循环

最终结果：[2,1,4,3]

关键技巧总结

1. 虚拟头节点：避免了对头节点的特殊处理
2. 循环条件设计：确保有足够的节点可以交换
3. 指针操作顺序：先断后连，避免节点丢失
4. 指针移动：每次移动到已处理部分的末尾

这个解法时间复杂度O(n)，空间复杂度O(1)，是一个非常优雅的迭代解法。