GU𝐆𝐫𝐨𝐰 𝐔𝐩
返回文章列表
数据结构与算法
算法链表学习路线

链表专题导读

从这一篇开始，我们进入链表专题。链表是面试中出现频率极高的基础数据结构，它的代码量通常不大，但对指针操作的严谨性要求很高——很多人不是不会思路，而是写代码时把指针改乱了。这个专题的目标就是：把链表的经典模型逐个吃透，形成一套稳定的做题套路。

一、链表是什么

数组在内存中是一段连续的空间，靠下标定位元素；链表则相反，节点散落在内存各处，靠每个节点里存的**引用（指针）**串起来。正因为不要求连续存储，链表的插入和删除只需要改几个引用，不必像数组那样整体搬移元素。

1.1 单链表

单链表的每个节点包含两部分：存值的 val 和指向后继的 next。这是刷题中最常见的形式。

public class ListNode {
    int val;
    ListNode next;
 
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

1.2 双链表

双链表在单链表基础上多了一个前驱指针 prev，既能向后走也能向前走。代价是每个节点多维护一个引用，删除某个给定节点时不再需要先找到它的前驱。

public class DoublyListNode {
    int val;
    DoublyListNode prev; // 指向前驱
    DoublyListNode next; // 指向后继
}

1.3 循环链表

把链表尾节点的 next 指回头节点，就得到循环链表。它适合"从任意节点出发都能遍历全表"的场景，经典应用是约瑟夫环问题。环形链表判环的相关题目（141/142）讨论的正是"链表中意外出现了环"这种结构。

三种结构一图总结：

单链表:   [1] -> [2] -> [3] -> [4] -> null
双链表:   null <- [1] <=> [2] <=> [3] -> null
循环链表: [1] -> [2] -> [3] ─┐
           ^─────────────────┘

二、链表 vs 数组：复杂度对比

操作 数组 链表
按下标访问 O(1) O(n)
按值查找 O(n) O(n)
插入/删除（已知位置） O(n)，需搬移后续元素 O(1)，只改引用
插入/删除（按值定位） O(n) O(n)，定位本身要遍历
内存布局 连续，可缓存友好 分散，每个节点有额外引用开销

两个容易误解的点：

  • "链表插入删除是 O(1)"有个前提——你已经站在目标位置上。如果还要先遍历找到位置，整体仍是 O(n)。
  • 数组的 O(n) 插入删除在数据量大、频繁增删时开销显著；而链表虽然增删快，但访问慢、缓存不友好，两者是取舍关系，不是谁全面碾压谁。

Java 里的 LinkedList 就是双链表实现，而日常开发中 ArrayList 反而更常用，因为多数场景下随机访问和遍历才是高频操作。

三、专题知识地图

链表的经典题目看似零散，其实可以归为几类核心模型。后面几篇文章会逐一展开，这里先建立整体认知：

模型 一句话思路 代表题
虚拟头结点 加一个哨兵节点，统一头结点与中间节点的操作逻辑 203、707
反转链表 双指针迭代或递归，逐个调转 next 方向 206
两两交换 借助 dummy，成对地"摘下两个、接回去" 24
删除倒数第 N 个 快慢指针，快指针先走 N 步拉开固定差距 19
链表相交 先对齐两链表长度，再同步前进找交点 160
环形链表 快 2 慢 1 判环，相遇后换起点找入环口 141、142

这几类模型的内在联系也值得注意：

  • 虚拟头结点是贯穿全文的通用技巧，几乎所有涉及头结点增删的题都可以用它简化边界处理；
  • 快慢指针在 19（删除倒数第 N 个）和 141/142（判环）中反复出现，只是"拉开差距"和"速度差"两种用法；
  • 反转不仅是独立题型，还是回文链表、K 个一组反转等题的子步骤。

四、LeetCode 题单清单

按推荐学习顺序整理如下，建议按表从上往下刷：

题号 题名 一句话考点
203 移除链表元素 虚拟头结点简化删除头结点的特例
707 设计链表 综合练增删查改，index 边界处理是重点
206 反转链表 双指针迭代反转，链表题的基本功
24 两两交换链表中的节点 dummy + 成对操作，指针修改顺序敏感
19 删除链表的倒数第 N 个节点 快慢指针拉开 N 步差距，一趟完成
160 相交链表 先对齐长度差，再同步走找交点
141 环形链表 快慢指针判环，快 2 慢 1 必相遇
142 环形链表 II 相遇点到入环点的数学推导

五、学习方法建议

链表题最忌"看着答案觉得会了"。我的建议是：

  1. 先画图再写码。每道题先把节点和箭头画出来，标注每一步哪个引用被改、改成什么。指针操作顺序错了，图上立刻能看出来。
  2. 先保存再修改。凡是改变 cur.next 之前，先想清楚它的旧值后面还要不要用，需要就用临时变量存下来。
  3. 边界自查。空链表、只有一个节点、操作头结点、操作尾节点，这四种情况都要在脑内（或纸上）跑一遍。
  4. 隔天重写。链表题手感退化很快，隔一两天不看答案重写一遍，能写对才算真掌握。

下一篇我们从最实用的技巧开始：虚拟头结点。

参考