写链表操作的时候你有没有被头节点折磨过insert、delete、reverse 这些函数写十次有八次前三分之一的代码全是在处理 head 为空、k 等于 0、要删的是第一个节点这些边界。出 bug 也全出在这些地方。后来我尝到了虚拟头节点的甜头——一个不存数据的占位节点能把所有头部的特判一次性抹平。这篇文章把虚拟头节点彻底聊透适合被链表边界 case 搞到头秃的初学者也想给已经会用但没用出味道的老手一点新思路。1. 没有虚拟头节点时链表操作是怎么地狱的1.1 头节点为什么总被特殊对待链表的每个节点都只有一个 next 指针这个结构决定了它的一个底层规律你想在某个位置插入或删除节点必须先找到这个位置的前驱节点。前驱的 next 指向哪个节点决定了这个位置在不在链上。问题来了头节点没有前驱。它之前什么东西都没有你在头部插入或者删除头节点时必须直接修改头指针本身而不是修改某个节点的 next 字段。换句话说链表的所有常规操作都建立在修改前驱的 next这个假设上头部偏偏打破了假设于是你的代码里就充满了if (head NULL)、if (k 0)、if (del head)这种补丁。单个补丁不难难的是补丁之间还会互相干扰。比如你先判断了 head 为空后面又判断 k 为 0再处理删除时 head 要不要更新这段逻辑写到后来你会发现真正干活的核心逻辑被挤得只剩三行其他全在防边界。1.2 一个带 k 的插入函数重现边界的痛苦我拿一个最常见的需求举例在单链表的第 k 个位置从 0 开始插入一个新节点插入成功后返回新的链表头。没有虚拟头节点的经典写法是这样struct ListNode* insertAt(struct ListNode* head, int k, int val) { if (k 0) { struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next head; return node; } struct ListNode* prev head; while (--k 0 prev ! NULL) { prev prev-next; } if (prev NULL) { return head; } struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next prev-next; prev-next node; return head; }你数数看这段代码里有多少个分支和返回值第一个if专门处理头部插入第二个if处理 k 越界的非法情况函数最后的返回值又要区分 head 变没变。这种代码在笔试里能过但在工程里经不起看逻辑分散调用者只要一个分支没记住就会在明明插到了头部但函数返回的还是旧 head这种错误上翻车。1.3 二级指针也不是银弹很多人尝试用二级指针来规避头部问题C 语言里确实可以这么写传入struct ListNode** head在函数内部统一通过*head来访问头指针。这个思路能解决修改头指针的传参问题但副作用也很明显void insertAt(struct ListNode** head, int k, int val) { struct ListNode** pp head; while (*pp ! NULL k 0) { pp ((*pp)-next); k--; } struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next *pp; *pp node; }这段代码其实已经很漂亮了pp指向的是一个指针字段的地址无论它是头指针变量还是某个节点的 next 字段操作方式完全一致。但代价是函数的签名变复杂了调用者必须记得传地址函数里还必须时刻脑子里绷着一根弦——pp现在指向的是头指针变量还是某个节点的 next。写两层指针的代码可读性在团队里会迅速下降尤其是新人接手的时候非常容易看晕。有没有更朴素的办法当然有那就是本文的主角虚拟头节点。2. 虚拟头节点的原理用占位换掉所有特判2.1 dummy 节点到底是什么虚拟头节点英文一般叫 dummy node 或者哨兵节点sentinel node本质就是一个不存储有效数据的节点作为链表的人工前驱挂在真正头节点的前面。struct ListNode dummy; dummy.next head;就这么两行链表从没有前驱变成了有前驱而且这个前驱永远存在、永远在头部之前。之后你所有针对头部的操作都变成了针对 dummy.next 的操作。你可能会问这不就是多了一个没用的节点吗关键点在于dummy 的存在让头部和中间位置失去了区别。头部插入和中间插入现在走完全一样的代码路径找到某个节点的前驱改前驱的 next。对编程来说统一永远比追求极致的空间节约重要一个 int 值的内存甚至不存储有效数据换来的是一大堆 if 分支的消失这笔账怎么算都划算。2.2 操作前驱是链表操作的本质链表操作本质上就一句话定位到目标节点的前驱然后动它的 next。插入是让前驱的 next 改成新节点删除是让前驱的 next 越位指向后继。只要你能把前驱找对后面的逻辑都是机械式操作。没有虚拟头节点时头节点没有前驱你只好单独给头节点开后门。有了虚拟头节点head 已经有了前驱 dummy所以任何位置都不再特殊。这在算法思想上有一个比较优雅的概括人为创造结构上的一致性来消除逻辑上的分支。这个思路不只是链表里用得到很多数据结构的实现里都能看到类似做法比如线段树的虚拟叶子节点、图算法里的超级源点本质都是加一个辅助元素让问题归一化。2.3 哪个坑被填平了从 head 到 dummy.next还有一个经常被忽视的好处函数的返回值变了。没有虚拟头节点时如果头部被插入或者删除原 head 指针就失效了你必须小心翼翼地回传新的 head或者狼狈地使用二级指针。用虚拟头节点时情况一下子清爽起来函数无论如何只需要返回 dummy.next这个值必然是新链表的头节点。不管你操作了哪个位置返回逻辑都无需变化。这个优势在写删除所有等于某个值的节点反转链表这类操作时尤其明显。你最后只需要写一行return dummy.next;所有针对头节点的担心全部消失。很多人在 LeetCode 上看到官方题解里带头节点的写法时觉得多此一举真到自己在工程中写链表工具类的时候才明白这一行 return 背后的确定性有多舒服。3. 三语言实操插入、删除、遍历的对照写法3.1 C 语言dummy 用栈上变量千万别 mallocC 语言是讲虚拟头节点最原汁原味的地方因为 C 里没有 class数据结构和函数完全分离头指针管理只能靠人肉维护最容易翻车。我用 C 语言实现一个带 k 的插入你看和前面那段没有虚拟头的版本对比有多大差异struct ListNode* insertAt(struct ListNode* head, int k, int val) { struct ListNode dummy; dummy.next head; struct ListNode* prev dummy; while (k 0 prev-next ! NULL) { prev prev-next; k--; } struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next prev-next; prev-next node; return dummy.next; }整个函数里只有一个if/else都没有头部插入 k0 的情况直接自然落到prev dummy不需要任何特判。越界情况由 while 循环的prev-next ! NULL天然兜住。返回值也统一了。提示dummy 节点推荐直接声明成局部变量栈上分配不要用malloc堆分配。因为局部变量会自动释放而malloc出来的 dummy 节点如果你在 return 前忘了 free每次调用都会泄漏一个节点。栈上变量还顺带避免了释放顺序错误这种头疼问题。删除节点同样简单只需要把插入逻辑里的构建新节点部分换成摘除目标节点struct ListNode* removeAt(struct ListNode* head, int k) { struct ListNode dummy; dummy.next head; struct ListNode* prev dummy; while (k 0 prev-next ! NULL) { prev prev-next; k--; } if (prev-next ! NULL) { struct ListNode* del prev-next; prev-next del-next; free(del); } return dummy.next; }注意这里删除的是前驱的下一个节点所以 while 循环的终止条件是prev-next ! NULL而不是prev ! NULL。这个细节值得在注释里写清楚因为在prev已经走到最后一个节点时prev-next是 NULL你不能去free一个空指针。3.2 C 模板类长期占位的 dummy 节点设计C 里写链表类虚拟头节点还有一个更高级的用法把它作为链表对象的永久成员变量让整个类从头到尾都不需要特判空链表。templatetypename T class LinkedList { public: LinkedList() : dummy_(new Node(T())) {} ~LinkedList() { Node* cur dummy_; while (cur ! nullptr) { Node* nxt cur-next; delete cur; cur nxt; } } void insert(int pos, const T val) { Node* prev dummy_; while (pos 0 prev-next ! nullptr) { prev prev-next; --pos; } Node* node new Node(val, prev-next); prev-next node; } void remove(int pos) { Node* prev dummy_; while (pos 0 prev-next ! nullptr) { prev prev-next; --pos; } if (prev-next ! nullptr) { Node* del prev-next; prev-next del-next; delete del; } } void print() const { for (Node* cur dummy_-next; cur ! nullptr; cur cur-next) { std::cout cur-data ; } std::cout std::endl; } private: struct Node { T data; Node* next; Node(const T d, Node* n nullptr) : data(d), next(n) {} }; Node* dummy_; };这里的dummy_不是每次操作临时创建而是链表对象创建时就准备好一直用到析构。这样一来空链表和非空链表的操作路径完全一致insert往头部插、往中间插、往尾部插都是同一套逻辑。这个设计在写工业级的链表链式哈希表、内存池链表时非常常见本质是把虚节点升级成了常驻哨兵。注意当你把链表做成模板类时需要保证 T 类型可以默认构造因为dummy_节点必须有一个默认值。如果你是严谨的模板库作者可能不希望强加这个约束那可以把 Node 拆成一个不含数据域的基类把 data 放在派生类里dummy 只继承基类。不过在实际工程里绝大多数链表的元素类型都是 int、指针、string 这类默认可构造的类型直接用T()就够了。3.3 Pythonprev dummy 的动态指针Python 的链表没有指针语法但这不妨碍虚拟头节点的思想落地。Python 里唯一要注意的是你封装一个 ListNode 类然后让prev先指向 dummy再通过prev.next来串联。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def remove_all_value(head: ListNode, target: int) - ListNode: 删除链表中所有值等于 target 的节点 dummy ListNode(0) dummy.next head prev, cur dummy, head while cur: if cur.val target: prev.next cur.next else: prev cur cur cur.next return dummy.next这个函数最典型的场景就是链表里多个节点的值都等于 target包括头节点。没有 dummy 时你得先单独处理头部一连串等于 target 的情况写一个 while 循环挪 head然后再处理中间节点。有了 dummy头节点不过就是prev.next的其中一环代码完全不需要关心 head 的移动。头节点的值等于 target第一次进入循环cur是原 headcur.val target于是prev.next cur.next而prev就是 dummydummy.next 指向原 head 的下一个节点。如果整个链表全是 target 节点循环结束后 dummy.next 会是 None函数返回None完美的空链表语义。3.4 用不用虚拟头一张表看清差距我整理了一个对照表帮助大家直观感受一下虚拟头节点在典型操作里省掉了什么操作场景无虚拟头节点的做法有虚拟头节点的做法核心差异头部插入单独 if 分支改 head直接统一prev dummy少一个分支头部删除先保护旧 head再把 head 后移prev-next prev-next-next少一个头指针更新删除所有等于 target 的节点先用 while 跳过头部匹配节点直接用 prev dummy 统一遍历少一个预处理循环在第 k 个位置插入区分 k0 和非 0while 循环自动处理返回值统一为 dummy.next反转链表头插法需要维护头部每个节点插到 dummy 后面代码更直观合并两个有序链表要判断 tail 是否为空tail 初始指向 dummy少一个空判断只读遍历直接从头遍历不需要用虚拟头无差异别硬用这张表最后一行很重要虚拟头节点解决的是结构性头部特判不是所有场景的银弹。纯遍历不改结构你不需要 dummy。4. 进阶场景三个用虚拟头写出漂亮解法的经典题4.1 反转链表把每个节点插到 dummy 后面反转链表是面试高频题最常见的迭代解法是维护两个指针 pre 和 cur 逐个反转 next 方向。但还有一个更符合本文气质的解法头插法反转。思路非常简单——依次摘下原链表的每个节点把它插入到 dummy 节点和 dummy.next 之间。每插一个最新节点就跑到了最前面走完整个链表顺序自然反转。ListNode* reverseList(ListNode* head) { ListNode dummy(0); ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 先保存后继否则断了找不到 cur-next dummy.next; // 新节点的下一个指向当前链表头部 dummy.next cur; // 新节点变成当前链表头部 cur nxt; } return dummy.next; }这个解法的绝妙之处在于你不需要记住三个指针的联动细节。dummy.next始终指向已反转部分的当前头每次摘一个节点放到它的前面等价于把头部前插了。理解它只需要想到一句话头部不断被新节点顶替顺序就被倒过来了。没有虚拟头的头插法要先在循环外把 head 拆出来费半天劲有了 dummy从头到尾就一个循环。这也是我向刚学链表反转的人推荐这种写法的原因思维负担小很多。4.2 删除倒数第 N 个节点快慢指针从 dummy 起步LeetCode 第 19 题删除链表的倒数第 N 个节点是个很典型的快慢指针 虚拟头组合题。思路是这样fast 先走 n 步然后 fast 和 slow 一起走当 fast 走到最后一个节点时slow 正好停在要删除节点的前驱。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next head; ListNode* fast dummy; ListNode* slow dummy; while (n-- 0) { fast fast-next; // fast 先走 n 步 } while (fast-next ! nullptr) { fast fast-next; slow slow-next; } ListNode* del slow-next; slow-next slow-next-next; delete del; return dummy.next; }关键在fast和slow都从dummy出发而不是从 head 出发。如果从 head 出发当要删除的是头节点时slow 会停不下来你不得不再加一堆特判。从 dummy 出发slow 天然指向待删除节点的前驱算法的不变式非常漂亮slow 永远不会是待删除节点本身而永远是它的前驱所以删除操作永远安全。为什么fast要从 dummy 而不是 head 出发你可以试着推演一下链表只有 1 个节点n1要删除这个唯一节点。fast 从 dummy 走一步指向 head第一个循环结束后 fast 指向唯一节点且 fast-next 为 NULL第二个循环不进入slow 还是 dummy然后删除 slow-next正好是那个唯一节点。如果 fast 从 head 出发第一个循环后 fast 已经是 NULL 了紧接着访问 fast-next 就会崩溃。4.3 合并两个有序链表tail dummy 的尾插法合并两个有序链表的递归写法很优雅但迭代写法更能展示虚拟头节点在尾插法里的作用。我们需要不断从两条链里挑出较小节点接到结果链尾部。ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! nullptr) ? l1 : l2; return dummy.next; }没有 dummy 时tail初始是 NULL循环里接第一个节点时你得先判断tail NULL然后单独给结果头赋值再从第二个节点开始走统一逻辑。这个第一次需要特殊处理的困境和头部插入一模一样。dummy 把结果链的当前尾部初始化为dummy让第一个节点也变成普通节点统一代码路径。我特别喜欢这个例子的原因是它展示的是一种通用技巧当你需要一个累加器式的结果链时dummy 是最自然的空起点。链表题里凡是一边遍历一遍串结果的题目都可以默认把结果链的尾指针初始化为指向 dummy包括链表加法、重排链表、链表排序等。5. 虚拟头节点不是万能的边界、误用与我的心得5.1 返回 dummy.next别回传原来的 head这是使用虚拟头节点的人最常踩的坑。你函数开头写了dummy.next head在中途可能已经修改了 dummy.next 指向的节点尤其是删除头部节点时。如果函数最后返回的是最初传入的 head 变量那么返回的可能是一个已经 free 掉的悬空指针或者是被跳过的不再属于链表的节点。正确的习惯是只要你创建了 dummy函数返回就永远写return dummy.next;不要回头看旧的 head。这是一种纪律性的写法和代码逻辑无关。哪怕是头部没有任何操作的函数只要创建了 dummy也建议统一返回 dummy.next保证代码的一致性防止后续有人改了扩充逻辑后忘记更新返回值。5.2 内存管理的三个坑第一个坑前面说过了dummy 节点本身没有有效数据如果分配在堆上又忘了释放每次函数调用都会泄漏。所以我一般用栈上变量或者确保析构函数会统一释放。第二个坑是链接野指针新建一个 dummy 后必须立即执行dummy.next head。如果漏了这步dummy.next 可能是一个随机地址整个遍历和插入会瞬间崩溃而且 debug 起来很痛苦因为随机崩溃的位置往往和真实错误点离得很远。第三个坑藏在删除节点里。用 C 或 C 写链表时删除节点后要及时 free/delete。正确顺序是先备份待删节点指针然后让前驱的 next 跳过它最后再释放那个指针。不要反过来也不要释放后继续访问它。比如前面removeNthFromEnd中delete del;必须放在slow-next slow-next-next;之后因为一旦 delete后续访问del-next就是未定义行为。提示调试链表程序的时候我最推荐的方式是先把整条链表的打印函数写出来打印从 dummy.next 开始的所有节点并且每操作一步都打印一次当前链表。结构问题通常在打印结果里一眼就能看出来比如少了一个节点顺序不对出现了循环。5.3 什么时候别用虚拟头节点虚拟头节点不是为了存在而存在的以下几种情况我反而不建议硬套只读操作查找某个值、遍历输出、求链表长度都不修改结构用不上 dummy。硬创建一个 dummy 反而让代码多了一行没有意义的赋值。需要保留原始头指针的场景如果这链表是全局变量多个函数共享同一个 head 指针而你的函数只是局部调整并不打算改变外部头指针那么用不用 dummy 取决于你会不会动头部。但要注意如果你用了 dummy 并且确实删掉了原 head外部那个全局 head 就失效了你必须主动更新它不能指望调用方自动知道。双向链表双向链表通常自带真正的头节点学数据结构时的带头双向循环链表这个头节点既是哨兵又是尾节点的连接点它的地位和单链表的虚拟前驱不完全一样。双链表里再做一层 dummy 反而是多余设计。Circular list 判断如果你在做快慢指针判环不需要改动结构直接用原链表判断即可。虚拟头节点在这里毫无帮助。我自己的判断方法是问一句函数返回的头节点会不会和传入的头节点不同如果有可能不同用虚拟头如果一定相同不用也完全可以。这个方法准确率很高基本能覆盖 90% 的链表函数设计场景。5.4 我写链表代码时的几个习惯最后分享几个我从实际工程踩坑中沉淀下来的小习惯纯经验之谈先画图再写代码。链表题最容易错的不是语法而是多个指针的先后顺序。纸上画出Dummy - head - ...的图标出每一步要改哪个指针写代码时照着图连。反正我在白板上画完图后再写代码基本不再出断链的问题。新节点接入时先连后断。插入一个新节点 node 时永远先做node-next prev-next再做prev-next node。这个顺序保证链不会断。把遍历终止条件写清楚再动手。你是希望循环停在某个节点上还是停在它的前驱上不同操作需要的终止条件不一样。插入和删除通常停在待操作位置的前一个也就是while (pos 0 prev-next ! NULL)。必要时用const和引用限定接口。C 里只读遍历的成员函数记得const插入删除的接口参数必要时传引用减少误用。统一命名。我习惯把虚拟头节点命名成dummy把游标命名成prev/cur/tail这个命名一旦定下来换到任何一道题都不用重新脑内翻译。虚拟头节点不是什么高深技术本质上就是一个为头节点造前驱的小 trick。但就是这个小 trick能让代码少掉大量分支让返回值变得确定让反转、合并、删除倒数第 N 个节点这些经典场景的代码写得像诗一样整齐。平时写链表代码的时候试着把要不要新建一个 dummy当成默认动作形成肌肉记忆你会回来感谢它的。 虚拟头节点：彻底告别链表操作的边界地狱
写链表操作的时候你有没有被头节点折磨过insert、delete、reverse 这些函数写十次有八次前三分之一的代码全是在处理 head 为空、k 等于 0、要删的是第一个节点这些边界。出 bug 也全出在这些地方。后来我尝到了虚拟头节点的甜头——一个不存数据的占位节点能把所有头部的特判一次性抹平。这篇文章把虚拟头节点彻底聊透适合被链表边界 case 搞到头秃的初学者也想给已经会用但没用出味道的老手一点新思路。1. 没有虚拟头节点时链表操作是怎么地狱的1.1 头节点为什么总被特殊对待链表的每个节点都只有一个 next 指针这个结构决定了它的一个底层规律你想在某个位置插入或删除节点必须先找到这个位置的前驱节点。前驱的 next 指向哪个节点决定了这个位置在不在链上。问题来了头节点没有前驱。它之前什么东西都没有你在头部插入或者删除头节点时必须直接修改头指针本身而不是修改某个节点的 next 字段。换句话说链表的所有常规操作都建立在修改前驱的 next这个假设上头部偏偏打破了假设于是你的代码里就充满了if (head NULL)、if (k 0)、if (del head)这种补丁。单个补丁不难难的是补丁之间还会互相干扰。比如你先判断了 head 为空后面又判断 k 为 0再处理删除时 head 要不要更新这段逻辑写到后来你会发现真正干活的核心逻辑被挤得只剩三行其他全在防边界。1.2 一个带 k 的插入函数重现边界的痛苦我拿一个最常见的需求举例在单链表的第 k 个位置从 0 开始插入一个新节点插入成功后返回新的链表头。没有虚拟头节点的经典写法是这样struct ListNode* insertAt(struct ListNode* head, int k, int val) { if (k 0) { struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next head; return node; } struct ListNode* prev head; while (--k 0 prev ! NULL) { prev prev-next; } if (prev NULL) { return head; } struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next prev-next; prev-next node; return head; }你数数看这段代码里有多少个分支和返回值第一个if专门处理头部插入第二个if处理 k 越界的非法情况函数最后的返回值又要区分 head 变没变。这种代码在笔试里能过但在工程里经不起看逻辑分散调用者只要一个分支没记住就会在明明插到了头部但函数返回的还是旧 head这种错误上翻车。1.3 二级指针也不是银弹很多人尝试用二级指针来规避头部问题C 语言里确实可以这么写传入struct ListNode** head在函数内部统一通过*head来访问头指针。这个思路能解决修改头指针的传参问题但副作用也很明显void insertAt(struct ListNode** head, int k, int val) { struct ListNode** pp head; while (*pp ! NULL k 0) { pp ((*pp)-next); k--; } struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next *pp; *pp node; }这段代码其实已经很漂亮了pp指向的是一个指针字段的地址无论它是头指针变量还是某个节点的 next 字段操作方式完全一致。但代价是函数的签名变复杂了调用者必须记得传地址函数里还必须时刻脑子里绷着一根弦——pp现在指向的是头指针变量还是某个节点的 next。写两层指针的代码可读性在团队里会迅速下降尤其是新人接手的时候非常容易看晕。有没有更朴素的办法当然有那就是本文的主角虚拟头节点。2. 虚拟头节点的原理用占位换掉所有特判2.1 dummy 节点到底是什么虚拟头节点英文一般叫 dummy node 或者哨兵节点sentinel node本质就是一个不存储有效数据的节点作为链表的人工前驱挂在真正头节点的前面。struct ListNode dummy; dummy.next head;就这么两行链表从没有前驱变成了有前驱而且这个前驱永远存在、永远在头部之前。之后你所有针对头部的操作都变成了针对 dummy.next 的操作。你可能会问这不就是多了一个没用的节点吗关键点在于dummy 的存在让头部和中间位置失去了区别。头部插入和中间插入现在走完全一样的代码路径找到某个节点的前驱改前驱的 next。对编程来说统一永远比追求极致的空间节约重要一个 int 值的内存甚至不存储有效数据换来的是一大堆 if 分支的消失这笔账怎么算都划算。2.2 操作前驱是链表操作的本质链表操作本质上就一句话定位到目标节点的前驱然后动它的 next。插入是让前驱的 next 改成新节点删除是让前驱的 next 越位指向后继。只要你能把前驱找对后面的逻辑都是机械式操作。没有虚拟头节点时头节点没有前驱你只好单独给头节点开后门。有了虚拟头节点head 已经有了前驱 dummy所以任何位置都不再特殊。这在算法思想上有一个比较优雅的概括人为创造结构上的一致性来消除逻辑上的分支。这个思路不只是链表里用得到很多数据结构的实现里都能看到类似做法比如线段树的虚拟叶子节点、图算法里的超级源点本质都是加一个辅助元素让问题归一化。2.3 哪个坑被填平了从 head 到 dummy.next还有一个经常被忽视的好处函数的返回值变了。没有虚拟头节点时如果头部被插入或者删除原 head 指针就失效了你必须小心翼翼地回传新的 head或者狼狈地使用二级指针。用虚拟头节点时情况一下子清爽起来函数无论如何只需要返回 dummy.next这个值必然是新链表的头节点。不管你操作了哪个位置返回逻辑都无需变化。这个优势在写删除所有等于某个值的节点反转链表这类操作时尤其明显。你最后只需要写一行return dummy.next;所有针对头节点的担心全部消失。很多人在 LeetCode 上看到官方题解里带头节点的写法时觉得多此一举真到自己在工程中写链表工具类的时候才明白这一行 return 背后的确定性有多舒服。3. 三语言实操插入、删除、遍历的对照写法3.1 C 语言dummy 用栈上变量千万别 mallocC 语言是讲虚拟头节点最原汁原味的地方因为 C 里没有 class数据结构和函数完全分离头指针管理只能靠人肉维护最容易翻车。我用 C 语言实现一个带 k 的插入你看和前面那段没有虚拟头的版本对比有多大差异struct ListNode* insertAt(struct ListNode* head, int k, int val) { struct ListNode dummy; dummy.next head; struct ListNode* prev dummy; while (k 0 prev-next ! NULL) { prev prev-next; k--; } struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next prev-next; prev-next node; return dummy.next; }整个函数里只有一个if/else都没有头部插入 k0 的情况直接自然落到prev dummy不需要任何特判。越界情况由 while 循环的prev-next ! NULL天然兜住。返回值也统一了。提示dummy 节点推荐直接声明成局部变量栈上分配不要用malloc堆分配。因为局部变量会自动释放而malloc出来的 dummy 节点如果你在 return 前忘了 free每次调用都会泄漏一个节点。栈上变量还顺带避免了释放顺序错误这种头疼问题。删除节点同样简单只需要把插入逻辑里的构建新节点部分换成摘除目标节点struct ListNode* removeAt(struct ListNode* head, int k) { struct ListNode dummy; dummy.next head; struct ListNode* prev dummy; while (k 0 prev-next ! NULL) { prev prev-next; k--; } if (prev-next ! NULL) { struct ListNode* del prev-next; prev-next del-next; free(del); } return dummy.next; }注意这里删除的是前驱的下一个节点所以 while 循环的终止条件是prev-next ! NULL而不是prev ! NULL。这个细节值得在注释里写清楚因为在prev已经走到最后一个节点时prev-next是 NULL你不能去free一个空指针。3.2 C 模板类长期占位的 dummy 节点设计C 里写链表类虚拟头节点还有一个更高级的用法把它作为链表对象的永久成员变量让整个类从头到尾都不需要特判空链表。templatetypename T class LinkedList { public: LinkedList() : dummy_(new Node(T())) {} ~LinkedList() { Node* cur dummy_; while (cur ! nullptr) { Node* nxt cur-next; delete cur; cur nxt; } } void insert(int pos, const T val) { Node* prev dummy_; while (pos 0 prev-next ! nullptr) { prev prev-next; --pos; } Node* node new Node(val, prev-next); prev-next node; } void remove(int pos) { Node* prev dummy_; while (pos 0 prev-next ! nullptr) { prev prev-next; --pos; } if (prev-next ! nullptr) { Node* del prev-next; prev-next del-next; delete del; } } void print() const { for (Node* cur dummy_-next; cur ! nullptr; cur cur-next) { std::cout cur-data ; } std::cout std::endl; } private: struct Node { T data; Node* next; Node(const T d, Node* n nullptr) : data(d), next(n) {} }; Node* dummy_; };这里的dummy_不是每次操作临时创建而是链表对象创建时就准备好一直用到析构。这样一来空链表和非空链表的操作路径完全一致insert往头部插、往中间插、往尾部插都是同一套逻辑。这个设计在写工业级的链表链式哈希表、内存池链表时非常常见本质是把虚节点升级成了常驻哨兵。注意当你把链表做成模板类时需要保证 T 类型可以默认构造因为dummy_节点必须有一个默认值。如果你是严谨的模板库作者可能不希望强加这个约束那可以把 Node 拆成一个不含数据域的基类把 data 放在派生类里dummy 只继承基类。不过在实际工程里绝大多数链表的元素类型都是 int、指针、string 这类默认可构造的类型直接用T()就够了。3.3 Pythonprev dummy 的动态指针Python 的链表没有指针语法但这不妨碍虚拟头节点的思想落地。Python 里唯一要注意的是你封装一个 ListNode 类然后让prev先指向 dummy再通过prev.next来串联。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def remove_all_value(head: ListNode, target: int) - ListNode: 删除链表中所有值等于 target 的节点 dummy ListNode(0) dummy.next head prev, cur dummy, head while cur: if cur.val target: prev.next cur.next else: prev cur cur cur.next return dummy.next这个函数最典型的场景就是链表里多个节点的值都等于 target包括头节点。没有 dummy 时你得先单独处理头部一连串等于 target 的情况写一个 while 循环挪 head然后再处理中间节点。有了 dummy头节点不过就是prev.next的其中一环代码完全不需要关心 head 的移动。头节点的值等于 target第一次进入循环cur是原 headcur.val target于是prev.next cur.next而prev就是 dummydummy.next 指向原 head 的下一个节点。如果整个链表全是 target 节点循环结束后 dummy.next 会是 None函数返回None完美的空链表语义。3.4 用不用虚拟头一张表看清差距我整理了一个对照表帮助大家直观感受一下虚拟头节点在典型操作里省掉了什么操作场景无虚拟头节点的做法有虚拟头节点的做法核心差异头部插入单独 if 分支改 head直接统一prev dummy少一个分支头部删除先保护旧 head再把 head 后移prev-next prev-next-next少一个头指针更新删除所有等于 target 的节点先用 while 跳过头部匹配节点直接用 prev dummy 统一遍历少一个预处理循环在第 k 个位置插入区分 k0 和非 0while 循环自动处理返回值统一为 dummy.next反转链表头插法需要维护头部每个节点插到 dummy 后面代码更直观合并两个有序链表要判断 tail 是否为空tail 初始指向 dummy少一个空判断只读遍历直接从头遍历不需要用虚拟头无差异别硬用这张表最后一行很重要虚拟头节点解决的是结构性头部特判不是所有场景的银弹。纯遍历不改结构你不需要 dummy。4. 进阶场景三个用虚拟头写出漂亮解法的经典题4.1 反转链表把每个节点插到 dummy 后面反转链表是面试高频题最常见的迭代解法是维护两个指针 pre 和 cur 逐个反转 next 方向。但还有一个更符合本文气质的解法头插法反转。思路非常简单——依次摘下原链表的每个节点把它插入到 dummy 节点和 dummy.next 之间。每插一个最新节点就跑到了最前面走完整个链表顺序自然反转。ListNode* reverseList(ListNode* head) { ListNode dummy(0); ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 先保存后继否则断了找不到 cur-next dummy.next; // 新节点的下一个指向当前链表头部 dummy.next cur; // 新节点变成当前链表头部 cur nxt; } return dummy.next; }这个解法的绝妙之处在于你不需要记住三个指针的联动细节。dummy.next始终指向已反转部分的当前头每次摘一个节点放到它的前面等价于把头部前插了。理解它只需要想到一句话头部不断被新节点顶替顺序就被倒过来了。没有虚拟头的头插法要先在循环外把 head 拆出来费半天劲有了 dummy从头到尾就一个循环。这也是我向刚学链表反转的人推荐这种写法的原因思维负担小很多。4.2 删除倒数第 N 个节点快慢指针从 dummy 起步LeetCode 第 19 题删除链表的倒数第 N 个节点是个很典型的快慢指针 虚拟头组合题。思路是这样fast 先走 n 步然后 fast 和 slow 一起走当 fast 走到最后一个节点时slow 正好停在要删除节点的前驱。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next head; ListNode* fast dummy; ListNode* slow dummy; while (n-- 0) { fast fast-next; // fast 先走 n 步 } while (fast-next ! nullptr) { fast fast-next; slow slow-next; } ListNode* del slow-next; slow-next slow-next-next; delete del; return dummy.next; }关键在fast和slow都从dummy出发而不是从 head 出发。如果从 head 出发当要删除的是头节点时slow 会停不下来你不得不再加一堆特判。从 dummy 出发slow 天然指向待删除节点的前驱算法的不变式非常漂亮slow 永远不会是待删除节点本身而永远是它的前驱所以删除操作永远安全。为什么fast要从 dummy 而不是 head 出发你可以试着推演一下链表只有 1 个节点n1要删除这个唯一节点。fast 从 dummy 走一步指向 head第一个循环结束后 fast 指向唯一节点且 fast-next 为 NULL第二个循环不进入slow 还是 dummy然后删除 slow-next正好是那个唯一节点。如果 fast 从 head 出发第一个循环后 fast 已经是 NULL 了紧接着访问 fast-next 就会崩溃。4.3 合并两个有序链表tail dummy 的尾插法合并两个有序链表的递归写法很优雅但迭代写法更能展示虚拟头节点在尾插法里的作用。我们需要不断从两条链里挑出较小节点接到结果链尾部。ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! nullptr) ? l1 : l2; return dummy.next; }没有 dummy 时tail初始是 NULL循环里接第一个节点时你得先判断tail NULL然后单独给结果头赋值再从第二个节点开始走统一逻辑。这个第一次需要特殊处理的困境和头部插入一模一样。dummy 把结果链的当前尾部初始化为dummy让第一个节点也变成普通节点统一代码路径。我特别喜欢这个例子的原因是它展示的是一种通用技巧当你需要一个累加器式的结果链时dummy 是最自然的空起点。链表题里凡是一边遍历一遍串结果的题目都可以默认把结果链的尾指针初始化为指向 dummy包括链表加法、重排链表、链表排序等。5. 虚拟头节点不是万能的边界、误用与我的心得5.1 返回 dummy.next别回传原来的 head这是使用虚拟头节点的人最常踩的坑。你函数开头写了dummy.next head在中途可能已经修改了 dummy.next 指向的节点尤其是删除头部节点时。如果函数最后返回的是最初传入的 head 变量那么返回的可能是一个已经 free 掉的悬空指针或者是被跳过的不再属于链表的节点。正确的习惯是只要你创建了 dummy函数返回就永远写return dummy.next;不要回头看旧的 head。这是一种纪律性的写法和代码逻辑无关。哪怕是头部没有任何操作的函数只要创建了 dummy也建议统一返回 dummy.next保证代码的一致性防止后续有人改了扩充逻辑后忘记更新返回值。5.2 内存管理的三个坑第一个坑前面说过了dummy 节点本身没有有效数据如果分配在堆上又忘了释放每次函数调用都会泄漏。所以我一般用栈上变量或者确保析构函数会统一释放。第二个坑是链接野指针新建一个 dummy 后必须立即执行dummy.next head。如果漏了这步dummy.next 可能是一个随机地址整个遍历和插入会瞬间崩溃而且 debug 起来很痛苦因为随机崩溃的位置往往和真实错误点离得很远。第三个坑藏在删除节点里。用 C 或 C 写链表时删除节点后要及时 free/delete。正确顺序是先备份待删节点指针然后让前驱的 next 跳过它最后再释放那个指针。不要反过来也不要释放后继续访问它。比如前面removeNthFromEnd中delete del;必须放在slow-next slow-next-next;之后因为一旦 delete后续访问del-next就是未定义行为。提示调试链表程序的时候我最推荐的方式是先把整条链表的打印函数写出来打印从 dummy.next 开始的所有节点并且每操作一步都打印一次当前链表。结构问题通常在打印结果里一眼就能看出来比如少了一个节点顺序不对出现了循环。5.3 什么时候别用虚拟头节点虚拟头节点不是为了存在而存在的以下几种情况我反而不建议硬套只读操作查找某个值、遍历输出、求链表长度都不修改结构用不上 dummy。硬创建一个 dummy 反而让代码多了一行没有意义的赋值。需要保留原始头指针的场景如果这链表是全局变量多个函数共享同一个 head 指针而你的函数只是局部调整并不打算改变外部头指针那么用不用 dummy 取决于你会不会动头部。但要注意如果你用了 dummy 并且确实删掉了原 head外部那个全局 head 就失效了你必须主动更新它不能指望调用方自动知道。双向链表双向链表通常自带真正的头节点学数据结构时的带头双向循环链表这个头节点既是哨兵又是尾节点的连接点它的地位和单链表的虚拟前驱不完全一样。双链表里再做一层 dummy 反而是多余设计。Circular list 判断如果你在做快慢指针判环不需要改动结构直接用原链表判断即可。虚拟头节点在这里毫无帮助。我自己的判断方法是问一句函数返回的头节点会不会和传入的头节点不同如果有可能不同用虚拟头如果一定相同不用也完全可以。这个方法准确率很高基本能覆盖 90% 的链表函数设计场景。5.4 我写链表代码时的几个习惯最后分享几个我从实际工程踩坑中沉淀下来的小习惯纯经验之谈先画图再写代码。链表题最容易错的不是语法而是多个指针的先后顺序。纸上画出Dummy - head - ...的图标出每一步要改哪个指针写代码时照着图连。反正我在白板上画完图后再写代码基本不再出断链的问题。新节点接入时先连后断。插入一个新节点 node 时永远先做node-next prev-next再做prev-next node。这个顺序保证链不会断。把遍历终止条件写清楚再动手。你是希望循环停在某个节点上还是停在它的前驱上不同操作需要的终止条件不一样。插入和删除通常停在待操作位置的前一个也就是while (pos 0 prev-next ! NULL)。必要时用const和引用限定接口。C 里只读遍历的成员函数记得const插入删除的接口参数必要时传引用减少误用。统一命名。我习惯把虚拟头节点命名成dummy把游标命名成prev/cur/tail这个命名一旦定下来换到任何一道题都不用重新脑内翻译。虚拟头节点不是什么高深技术本质上就是一个为头节点造前驱的小 trick。但就是这个小 trick能让代码少掉大量分支让返回值变得确定让反转、合并、删除倒数第 N 个节点这些经典场景的代码写得像诗一样整齐。平时写链表代码的时候试着把要不要新建一个 dummy当成默认动作形成肌肉记忆你会回来感谢它的。