手写链表全攻略：从LeetCode 707到嵌入式list_head

把链表从头实现一遍，是每个写代码的人都绕不过去的一道坎。无论是 LeetCode 707 这道经典的“设计链表”，还是数据结构实验课上的“单链表的基本操作实验”，底层逻辑都是一样的：你要自己管理节点、自己处理指针（或者引用）、自己保证边界条件不出错。“链表”这个关键词从大一听到毕业，从 C 语言结构体到 C++ 类模板，再到 Python 的 class、Java 的泛型，甚至嵌入式内核里的侵入式链表，本质上都是同一套思维。这篇我就围绕“设计链表”这个题目，把节点定义、带头结点与不带头结点的取舍、五个核心操作、逆置链表、循环单链表、嵌入式链表这些内容串起来讲一遍，顺带把我踩过的坑和常用的排查手法都交代清楚。

这篇内容适合刚学完指针想动手写链表的人，适合正在刷 LeetCode 准备面试的人，也适合想把内核里那种“没有数据域的链表”搞明白的嵌入式初学者。你会看到完整的可运行代码、边界条件的逐条分析，以及那些教科书里一般不会写的“为什么这里要这样写”。

1. 设计链表前需要想清楚的三件事

1.1 节点定义：一切接口的地基

不管你要实现的是单链表、循环单链表还是双向链表，第一步永远是定义节点。C 语言里最经典的写法是结构体：

typedef struct Node { int data; struct Node* next; } Node;

注意这里struct Node* next不能省略struct关键字，因为在结构体内部自引用时，Node这个 typedef 别名还没有生效。这是 C 语言新手最容易编译报错的地方之一。C++ 里写结构体就舒服多了，可以在结构体里直接写构造函数，这也是 LeetCode 默认的ListNode写法：

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) {} };

提供多个构造函数的原因很实际：new 一个节点的时候可以直接带上值，省得每次都先构造再赋值。如果不写构造函数，ListNode就是聚合类型，初始化时还得逐个字段赋值，代码看起来会很啰嗦。

Python 的节点通常用 class 实现：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

Java 则更强调泛型：

public class ListNode<E> { E val; ListNode<E> next; ListNode(E val) { this.val = val; } }

节点定义没有标准答案，但有一个原则是通用的：节点只负责存数据和指向下一个节点，不要在里面塞业务方法。链表本身的增删改查逻辑应该放在链表类或独立函数里，否则嵌套一多就分不清是谁在管理谁。

1.2 带头结点还是不带头结点：两种设计哲学

这个“头结点”指的是虚拟头结点（dummy node），不是第一个真正存数据的节点。带虚拟头结点的链表长这样：

dummy -> node1 -> node2 -> null

不带头结点的链表则是：

head -> node1 -> node2 -> null

很多人刚开始不理解为什么要多放一个 dummy，觉得纯属浪费空间。等你真去写删除头节点的逻辑就明白了：不带头结点时，删除第一个节点必须修改head指针本身，而删除其他节点只需要改前一个节点的next。这意味着你的 delete 函数里必须写一个if (head == target)的特判。带虚拟头结点之后，所有删除操作都变成了“找到目标节点的前驱，修改前驱的 next”，不再需要单独处理头节点。

而且带头结点还有一个附带好处：空链表和非空链表的结构统一了。空链表就是dummy->next == nullptr，插入第一个节点之前 dummy 就存在，不需要在 insert 前检查“链表是不是空”。

不带头结点也有它的应用场景。比如“不带头结点的单链表”在考研数据结构题里很常见，题目会故意不给你 dummy，考察的就是你对头指针更新的敏感度。再比如循环单链表，如果做“约瑟夫问题”，不带头结点反而更直观，因为头结点本身也是一个数据节点，删除时通过前驱指针找目标，和前文逻辑一样。

两种方案没有绝对优劣。日常开发、LeetCode 刷题、标准库实现，我建议一律带头结点，理由就一条：少写一半特判逻辑。如果是为了考试或面试手撕算法，两种都要会，尤其是“不带头结点时处理头节点”的那几个边界情况，必须在纸上画一遍。

1.3 侵入式还是非侵入式：嵌入式里的另类链表

大学课本里的链表是“非侵入式”的，因为节点里直接放数据域int data。但嵌入式内核（比如 Linux 内核）里的链表完全是另一套设计：节点结构体里不包含数据，只有next和prev两个指针，数据通过结构体嵌套的方式“长”在链表节点外面。

struct list_head { struct list_head *next, *prev; }; struct my_device { int irq; char name[32]; struct list_head list; // 这个字段负责把设备挂到链表上 };

这样做的最大好处是同一个list_head结构可以被任意类型复用。你把struct list_head嵌进任何一个结构体，那个结构体就自动拥有了被链表管理的能力，不需要为每一种数据类型重写一套插入删除函数。配合container_of宏，可以从list_head字段的地址反推出宿主结构体的起始地址：

#define container_of(ptr, type, member) \ ((type *)((char *)(ptr) - (char *)&((type *)0)->member))

原理很简单：结构体成员的地址减去成员在结构体里的偏移量，就是结构体的起始地址。看到“嵌入式链表代码示例”这个热搜词时，八成指的就是这种侵入式链表。它跟你刷题用的那种带头结点链表最大的不同是：嵌入式链表的头节点只是一个空的链头，不存业务数据，用list_for_each_entry遍历时自动跳过链头。

2. 核心细节：接口设计与索引规则

2.1 LeetCode 707 的五个接口到底在考什么

“设计链表”这道题要求实现get、addAtHead、addAtTail、addAtIndex、deleteAtIndex五个方法。表面看只是基本的增删查，实际上每一道题都在卡边界条件：

• get(index)：index 从 0 开始，如果 index 无效返回 -1。
• addAtHead(val)：在头部插入，相当于addAtIndex(0, val)。
• addAtTail(val)：在尾部插入，相当于addAtIndex(size, val)。
• addAtIndex(index, val)：如果 index 等于链表长度，插到尾部；如果 index 大于链表长度，什么都不做；如果 index 小于 0，按 0 处理。
• deleteAtIndex(index)：如果 index 有效，删除下标为 index 的节点。

这里面最容易被忽略的是“什么时候什么都不做”。很多人写addAtIndex时不管三七二十一，index 大于 size 也硬插，结果就是在链表中间凭空冒出空位。注意addAtIndex不是“在第 index 个位置后面插入”，而是“在第 index 个位置前面插入”。所以 index 的合法范围是[0, size]，等于 size 时就是尾插，大于 size 时直接 return。

2.2 用 dummy 统一插入和删除逻辑

带虚拟头结点时，addAtIndex(index, val)的通用做法是：先让一个cur指针从 dummy 出发，向后移动 index 步，此时cur恰好停在“要插入位置的前一个节点”，然后执行：

ListNode* newNode = new ListNode(val); newNode->next = cur->next; cur->next = newNode;

这里有个重要细节：cur从 dummy 出发，移动 index 步，而不是从 head 出发移动 index 步。因为 dummy 的下标是 -1，移动 index 步后指针落在下标 index - 1 的节点上，正好是插入位置的前驱。如果从 head 出发移动 index 步，得到的是下标 index 的节点本身，插入逻辑就要改成“在当前节点后面插”，容易把自己绕晕。

同样地，deleteAtIndex(index)也是让cur从 dummy 出发移动 index 步，然后：

ListNode* toDelete = cur->next; cur->next = toDelete->next; delete toDelete;

这样删除下标为 0 的节点时，cur就是 dummy，和删除中间节点是同一套代码，不需要写head = head->next这种特判。这种“统一逻辑”正是 dummy node 最大的价值，也是为什么我在刷题和写项目时几乎无脑带头结点。

2.3 遍历与逆序：一个正向，一个反向

链表遍历是最基本的操作，但很多人写循环链表的遍历时会栽跟头。普通单链表的遍历终止条件是p == nullptr，循环单链表的终止条件是p == head或者p->next == head，取决于你进入循环时 p 的位置。

逆置链表（逆序链表）是热搜词里的高频词，也是面试最爱问的手写题。以单链表的迭代逆序为例，核心思路是维护三个指针：pre、cur、nxt。每次循环做四件事：先保存cur->next，再把cur->next指向pre，然后把pre后移到cur，最后把cur后移到保存好的nxt。写成代码：

ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* nxt = cur->next; cur->next = pre; pre = cur; cur = nxt; } return pre; }

Python 版迭代写法更简洁：

def reverse_list(head): pre = None cur = head while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre

Python 的递归写法也很适合展示链表逆序的递归思路：

def reverse_list(head): if not head or not head.next: return head new_head = reverse_list(head.next) head.next.next = head head.next = None return new_head

递归法理解起来稍微绕一点，但它的核心只有一句：先逆置head.next为头结点的子链表，再把当前节点接在子链表末尾。递归法的空间复杂度是 O(n)，因为递归栈会占用空间，迭代法是 O(1)，所以工程实现优先迭代法，递归法更多用来考察思维。

3. 完整实操：用 C++ 实现带头结点的单链表

3.1 类骨架和成员变量

我用 C++ 把 LeetCode 707 完整实现一遍。先定义链表类，成员变量只有一个虚拟头结点和一个长度计数：

class MyLinkedList { private: ListNode* dummy; int size; public: MyLinkedList() : dummy(new ListNode(0)), size(0) {} int get(int index) { if (index < 0 || index >= size) return -1; ListNode* cur = dummy->next; for (int i = 0; i < index; i++) { cur = cur->next; } return cur->val; } void addAtHead(int val) { ListNode* newNode = new ListNode(val); newNode->next = dummy->next; dummy->next = newNode; size++; } void addAtTail(int val) { ListNode* cur = dummy; while (cur->next != nullptr) { cur = cur->next; } cur->next = new ListNode(val); size++; } void addAtIndex(int index, int val) { if (index > size) return; index = max(0, index); ListNode* cur = dummy; for (int i = 0; i < index; i++) { cur = cur->next; } ListNode* newNode = new ListNode(val); newNode->next = cur->next; cur->next = newNode; size++; } void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode* cur = dummy; for (int i = 0; i < index; i++) { cur = cur->next; } ListNode* toDelete = cur->next; cur->next = toDelete->next; delete toDelete; size--; } };

size成员必须维护，这关系到addAtIndex的合法性判断。如果不维护 size，每次加节点都要从头遍历一遍才能知道链表长度，时间复杂度从 O(1) 变成 O(n)。

3.2 五个方法的设计意图和运行过程

get(index)的循环从dummy->next开始，因为下标为 0 的节点就是第一个真实节点。如果从 dummy 开始，循环次数就要变成index + 1，虽然结果一样，但代码理解起来更别扭。

addAtHead最容易写错的地方是顺序。必须先让newNode->next指向原头节点，再把dummy->next指向 newNode。如果先改dummy->next，原头节点就丢了，新节点就变成指向自己，链表形成一个断环。这个错误几乎每个新手都犯过，最好的检查办法是在纸上画两个方框、两条线，动态推演一遍。

addAtTail没什么技巧，就是一直走到最后一个节点。注意这里不能用cur != nullptr作为循环条件，否则走出来 cur 是空指针，没法赋值了。

addAtIndex里我先做“index 大于 size 直接 return”的判断，再把负数 index 强制改成 0。这一步的顺序看起来很基础，但联合起来就是完整的边界处理：index 小于 0 时当成 0 处理，等于 size 时尾插，大于 size 时忽略。

deleteAtIndex最后的delete toDelete是 C++ 特有的，因为前面用了new创建节点。如果你写的是 Java、Python，这个释放动作由垃圾回收器处理，但 C++ 里不 delete 就是内存泄漏。LeetCode 判题环境不检查泄漏，但实际工程或者面试手写时会看重这一点。

3.3 扩展到循环单链表和双向链表

上面的设计改成循环单链表只需要改两处：初始化时dummy->next指向自身；插入和删除逻辑大部分复用，但头插和尾插的边界要额外小心。循环单链表遍历的终止条件是cur->next == dummy，而不是cur->next == nullptr。判断链表为空也变成dummy->next == dummy。

双向链表则要增加一个prev指针，节点定义为：

struct DListNode { int val; DListNode* prev; DListNode* next; DListNode(int x) : val(x), prev(nullptr), next(nullptr) {} };

双向链表插入节点时必须先连后面的指针再连前面的指针，推荐顺序是：先给 newNode 指定prev和next，再更新cur->next->prev = newNode，最后cur->next = newNode。这个顺序如果颠倒，很容易把cur->next弄丢。删除时则要先保存toDelete，然后更新toDelete->prev->next = toDelete->next，同时更新toDelete->next->prev = toDelete->prev，最终释放节点。

4. 常见问题与排查技巧实录

4.1 指针更新顺序错误

“链表插入”类操作里最常见的 bug 是更新顺序反了。我看到最多的情况是这样的：

// 错误示例 cur->next = newNode; newNode->next = cur->next; // 此时 cur->next 已经是 newNode 了

这个死循环和丢链的问题在 LeetCode 讨论区反复出现。我说个自己的排查经验：拿到一个链路问题，先在纸上画出插入前和插入后的两条线，然后把代码步骤对照着画，哪一步先走错一眼就看得出来。实在不想画图，就遵循一个万能口诀：“先接新来的，再改原来的”。也就是说，先把 newNode 的 next 指向正确位置，再修改前驱的 next。这个口诀对单链表插入、双向链表插入、循环链表插入都适用。

4.2 内存泄漏与悬空指针

C/C++ 手写链表最容易出现两个内存问题。

第一个是new了节点但没delete，表现为链表长度不断增加但程序不崩溃，跑久了内存慢慢涨上去。LeetCode 不检测这个，但你自己用 valgrind 或 ASan 跑一遍就会看到 memory leak 报告。

第二个是delete了节点但前置指针没断开，比如delete toDelete之后，前面持有的cur->next变成了原 toDelete 的地址，这是一个悬空指针。正确做法是先完成cur->next = toDelete->next，让链表结构断开，再 delete。

在做“逆置链表”时还有第三个坑：迭代逆序结束后，原头节点的 next 必须置空，否则链表里会残留一个指向第二个节点的环。改造后的链表尾部就是这个原头节点，它的 next 应该为 nullptr 而不是指向后一个节点。很多人在面试现场写逆置链表，最后一步漏了置空，链表变成环，遍历直接死循环，面试官一眼就看出问题。

4.3 常见问题速查表

4.4 实验课里“单链表基本操作”的完整验证套路

如果你是在用“单链表的基本操作实验”这个场景，建议按这个步骤验证代码正确性：

1. 创建一个空链表，打印 size 和 head 地址，确认 dummy 存在。
2. 依次 addAtHead(1)、addAtHead(2)，打印，确认头插顺序与预期一致。
3. 依次 addAtTail(3)、addAtTail(4)，打印，确认尾插顺序与预期一致。
4. addAtIndex(2, 5)，打印，确认插入位置正确。
5. deleteAtIndex(3)，打印，确认删除后长度减少 1。
6. get(0)、get(size-1)、get(-1)、get(size)，打印，确认边界返回值。
7. 写一个遍历函数，输出所有节点，若出现无限循环或重复元素，立刻检查指针操作。

这七步做完，基本可以把“设计链表”这个题目在实验课上的要求全部覆盖到。打印函数对调试来说非常值钱，比用断点还直观，尤其是检查循环链表的时候，设置一个节点计数上限（比如最多打印 20 个节点）可以保护你的终端不被死循环刷爆。

5. 场景延伸：逆置、循环链表与嵌入式实践

5.1 逆置链表的三套实现和选择建议

逆置链表（逆序链表）既然出现在热搜词里，我就多说一点。除了前面写过的迭代法和递归法，还有第三种思路：头插法重建。遍历原链表，每拿到一个节点，就把它头插到新链表头部：

ListNode* reverseList(ListNode* head) { ListNode* newHead = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* nxt = cur->next; cur->next = newHead; newHead = cur; cur = nxt; } return newHead; }

这段代码看着和迭代法很像，但思维角度不同：迭代法是就地翻转指针方向，头插法是“拆一个、挂一个”。头插法的好处是逻辑更符合人脑：每次把当前节点从旧链表中摘除，放到新链表最前面，循环结束时 newHead 就是逆序后的头。

Python 里还有一种利用列表切片的小技巧：

def reverse_list(head): vals = [] cur = head while cur: vals.append(cur.val) cur = cur.next dummy = ListNode(0) cur = dummy for v in reversed(vals): cur.next = ListNode(v) cur = cur.next return dummy.next

这种方法空间复杂度 O(n)，胜在代码极短、易读，适合比赛时快速验证思路，不适合生产环境。

5.2 循环单链表实现约瑟夫问题

循环单链表最典型的应用是约瑟夫问题。假设 n 个人围成一圈，从第一个人开始报数，报到 k 的人出列，接着从下一个人重新报数，直到只剩一个人。用不带头结点的循环单链表实现时，遍历逻辑会变得特别自然：

ListNode* josephus(int n, int k) { ListNode* head = new ListNode(1); ListNode* cur = head; for (int i = 2; i <= n; i++) { cur->next = new ListNode(i); cur = cur->next; } cur->next = head; // 成环 ListNode* prev = cur; ListNode* p = head; while (p->next != p) { for (int i = 1; i < k; i++) { prev = p; p = p->next; } prev->next = p->next; delete p; p = prev->next; } return p; }

这段代码有个隐藏细节：删除节点时必须有前驱指针prev，因为p是要删除的节点，光有p无法知道前驱是谁。所以每次报数时prev始终跟在p后面一步。循环链表的终止条件是p->next == p，即只剩自己的节点，此时它既是头也是尾，输出结果就可以了。这个题目能帮你把循环链表的前驱维护、节点删除、环终止条件一次练透。

5.3 嵌入式链表代码的取舍与工程习惯

嵌入式链表和刷题链表的最大不同不只是“侵入式”这一点，还有对动态内存分配的态度。刷题时new随便用，嵌入式环境里频繁malloc/free可能带来碎片化和不可预测的延迟，所以很多项目直接用静态数组模拟链表，或者用内存池预先分配固定数量的节点。

对于嵌入式开发初学链表，建议先在开发板上做一个小实验：定义一个结构体，挂一个list_head，写一个 driver 列表，模拟设备注册和注销。内核里定义一个链表：

LIST_HEAD(device_list);

然后每个驱动注册时把自己的 list_head 字段list_add_tail(&my_dev->list, &device_list)，遍历时用list_for_each_entry(dev, &device_list, list)拿到的是包含 list_head 的 struct my_device。这套写起来比 C 语言课本里的链表多了一层“字段嵌套”的抽象，但跑通一次之后，你对“链表管理的是节点而不是数据”这个说法会有非常深的理解。

嵌入式链表代码里最重要的习惯是：链表操作函数只动指针，不感知宿主结构体类型。也就是说，insert、delete、遍历这些函数永远只和struct list_head*打交道，宿主类型是 container_of 宏在遍历时才转换的。这样一套链表代码可以被所有需要链表的内核模块复用，不用为每一种设备类型重写一遍增删查。

最后分享两个小经验

第一，如果你刚开始学链表，不要只看代码，一定要亲手画图推演。头插法、尾插法、删除节点、逆置链表，每个操作都在纸上画两遍“前后状态图”，画完你会发现所有 bug 都变成了肉眼可见的线条冲突。我自己带过不少实习生，能准确画出插入前后两条链的同学，刷链表题目的出错率至少低一半。

第二，做完 LeetCode 707 之后，不要急着做下一题，把同样的类改成 Java 版，再用 Python 写一遍，最后模拟一遍“不带头结点的无头版”。语言切换能帮你把指针和引用的差异彻底想明白，无头版能帮你在没有虚拟头结点兜底的情况下重新审视边界条件。这三步做完，你对“链表”这个词的理解就能从“背模板”升级到“设计者”的层面。后续不管遇到循环单链表还是嵌入式 list_head，再看一眼结构就能知道该往哪里接指针。