C++链表核心操作与算法实战：从建节点到反转合并的完全指南

链表这东西，我在之前的练习记里提过一嘴，今天专门拎出来写一篇。原因很简单：链表在C++算法题里的出场率实在太高了，而且它和数组、vector那种“一段连续内存”的直觉完全不同，很多新手写起来特别容易栽跟头。我也是从一个个段错误、空指针崩溃里爬出来的，所以这篇就把我练习链表时反复折腾过的那些点一次性说清楚——怎么建节点、怎么遍历、怎么在指定位置插入、怎么反转、怎么找中间节点、怎么判环、怎么合并有序链表，最后再来点调试技巧和常见坑。这些内容看起来基础，但恰恰是后面刷二叉树、图、复杂模拟题的底座，值得认真过一遍。

这一篇针对的是已经有C++基本语法基础（至少知道结构体、指针、引用），但链表还没形成肌肉记忆的读者。如果你完全没碰过指针，建议先补一下指针和内存的基础，否则看下面的代码可能会有点吃力。我会尽量在关键地方解释明白，但指针的基本概念我不再展开。

好，直接进入正题。

1. 链表的两种C++实现方式：结构体裸指针 vs 智能指针

先说链表节点的定义。C++里最常见的两种写法，一种是传统的裸指针结构体，一种是C++11之后用智能指针。绝大多数算法训练和面试场景，用的都是裸指针结构体，所以这篇也主要围绕这种写法展开。

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

构造函数这里我建议一定要写。不写的话，每次新建节点都得手动赋值node->next = nullptr，一旦忘了，那个指针就是野指针，后面遍历的时候随机崩溃，排查起来非常折磨。用构造函数一次性把next初始化为nullptr，能省掉一大半低级错误。

另一种写法是用std::shared_ptr或者std::unique_ptr：

#include <memory> struct ListNode { int val; std::shared_ptr<ListNode> next; ListNode(int x) : val(x), next(nullptr) {} };

智能指针的好处是内存自动管理，不用手动delete，特别适合工程代码。但算法训练里我不推荐用，原因有三点：第一，写法啰嗦，每次操作都要.get()或者std::move，精力被分散；第二，shared_ptr循环引用会导致内存泄漏（链表成环时next互相引用，引用计数永远不为0），这反而引入新问题；第三，面试手写代码时，面试官通常默认看裸指针写法，你上来用智能指针，反而可能因为一些边界行为被追问到尴尬。

所以这篇的所有代码都用裸指针结构体，内存释放的部分我会在最后一节单独说明。

另外说一句，算法题中链表节点通常不带头结点，就是第一个节点就存储有效数据。有的教材喜欢搞一个不存数据的头结点来统一插入删除逻辑，这个后面我会单独聊它和“虚拟头结点”技巧的区别。

2. 单链表核心操作的C++实现：从创建到指定位置插入

2.1 创建链表：头插法和尾插法的差异

创建链表有两种基本策略：头插法和尾插法。头插法是把新节点插到链表头部，最后得到的链表顺序和输入顺序相反；尾插法是把新节点接到链表尾部，保持输入顺序。

尾插法练手时最常用，因为它能帮你把“找尾节点”“连接指针”这些基本动作练熟：

ListNode* createListTailInsert(const std::vector<int>& nums) { ListNode* dummy = new ListNode(0); // 临时头结点，后面细说 ListNode* cur = dummy; for (int num : nums) { cur->next = new ListNode(num); cur = cur->next; } return dummy->next; }

这里我用了dummy（哑结点/哨兵结点），它是算法里极其常见的小技巧：用一个不参与逻辑的节点，统一下一步的插入、删除逻辑。没有它的话，尾插法每插一个节点都得判断“链表是不是空的，头指针要不要更新”，代码会多出不少分支。

2.2 遍历链表与统计长度

遍历是所有链表操作的基础，原理很简单：从头指针开始，每次访问当前节点的数据，然后让指针指向next，直到指针为nullptr。

int getListLength(ListNode* head) { int len = 0; ListNode* cur = head; while (cur != nullptr) { ++len; cur = cur->next; } return len; }

这个代码谁都会写，但有一个高频bug我见过无数次：循环里写成了while (cur->next != nullptr)。这两者的区别是什么？cur != nullptr允许我们访问最后一个节点后再退出，而cur->next != nullptr会在最后一个节点处停下，统计出来的长度少1。很多人在“遍历”和“找尾节点”这两个场景里混用这两种判断条件，结果逻辑一团乱。我的经验是：需要访问每个节点的数据，就用cur != nullptr；只是要找到最后一个节点，才用cur->next != nullptr。

2.3 在指定位置插入节点：理解前驱节点

在指定位置插入节点是链表操作的经典问题，它和数组最大的不同就在这里。

数组中插入元素，得把后面的元素全部往后挪，时间复杂度O(n)，但物理上元素都在原地；链表中插入元素，只需要把前一个节点的next指向新节点，新节点的next指向原来的下一个节点，时间复杂度O(1)——前提是你已经找到了前驱节点。

但找前驱节点本身又是O(n)的，所以链表插入的整体复杂度还是O(n)。这一点初学者容易混淆，以为链表插入是O(1)，面试被问到时含含糊糊。准确的说法是：插入动作本身是O(1)，找到插入位置是O(n)，整体是O(n)。

下面是在第pos个位置插入节点（pos从0开始计数，即头节点是第0个）的实现：

ListNode* insertNode(ListNode* head, int pos, int val) { ListNode* newNode = new ListNode(val); // 特殊情况：插到头部 if (pos == 0) { newNode->next = head; return newNode; } ListNode* prev = head; // 找到第 pos-1 个节点，也就是新节点的前驱 for (int i = 0; i < pos - 1; ++i) { if (prev == nullptr) { // 位置非法：链表没那么长 delete newNode; return head; } prev = prev->next; } if (prev == nullptr) { delete newNode; return head; } newNode->next = prev->next; prev->next = newNode; return head; }

有几个细节值得提：

• 插入头部和插入中间要分开处理，因为头部插入需要更新头指针本身。这正是不带头结点的链表的麻烦之处。如果你在前面用dummy建链表，那么统一处理逻辑会更优雅，但这里为了展示“原地操作”的细节，我故意保留了分支。
• 循环里for (int i = 0; i < pos - 1; ++i)这一步，是在走pos-1步，跑到第pos-1个节点。写的时候脑子里要清楚：头节点是第0个节点，它的前驱是空；要插到第pos个位置，前驱是第pos-1个节点。位置和步数之间差1，这是链表题里最容易摔跤的地方。
• 如果位置越界，记得delete newNode。很多人写着写着就内存泄漏了，练习时无所谓，但养成好习惯后面受益。

上面这个写法每次插入头部都要单列逻辑，代码不优雅。所以实际刷题时，我更推荐用一个在所有场景下统一处理的套路——虚拟头结点。

2.4 虚拟头结点：让插入删除逻辑统一

虚拟头结点（dummy node）和带头结点的链表不是一回事。虚拟头结点是临时的，用完就丢；带头结点的链表是长久的结构设计。虚拟头结点的核心价值在于：它让你不需要特殊处理“操作发生在真实头节点”的情况。

ListNode* insertNodeUnified(ListNode* head, int pos, int val) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* prev = dummy; for (int i = 0; i < pos; ++i) { if (prev->next == nullptr) { // 位置越界 delete dummy; return head; } prev = prev->next; } ListNode* newNode = new ListNode(val); newNode->next = prev->next; prev->next = newNode; ListNode* newHead = dummy->next; delete dummy; return newHead; }

注意这里的循环条件变成了i < pos。为什么？因为prev的初始值是dummy，它相当于“第-1个节点”，前驱是它自己；要插到第pos个位置，preve要从dummy走pos步走到第pos-1个节点。这个技巧我第一次遇到时也愣了一下，但想通了之后就会觉得特别顺。

虚拟头结点在链表题里出场率极高，比如删除倒数第N个节点、合并两个链表、反转链表的一部分，都能靠它省掉大量边界判断。后面例题里我会反复用到。

3. 链表反转：迭代法与递归法

链表反转是必练题，几乎可以说没有之一。它的思路本身不难，但第一次写的人很容易被“指针断链”搞晕。

3.1 迭代法反转

反转的核心思想：遍历链表，把每个节点的next指向前一个节点。但这会导致原链表断裂，所以必须在改变next之前，先保存下一个节点。

ListNode* reverseListIterative(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* nextTemp = cur->next; // 先保存下一个节点 cur->next = prev; // 反转当前节点的指针 prev = cur; // prev 前移 cur = nextTemp; // cur 前移 } return prev; // 结束时 prev 指向原链表的最后一个节点，也就是新链表的头 }

这个代码第一次看会觉得绕，但多画几张图就好了。我建议初学的时候拿三个节点手动模拟一遍，把每一步的prev、cur、nextTemp指到哪儿画出来，比盯着代码看十遍都管用。

这里有个细节：反转后的头节点是prev，不是cur。循环结束时cur是nullptr，prev才是原链表的尾巴。很多人漏了这点，返回了cur，然后调试半天发现返回了个空指针。

3.2 递归法反转

递归法的写法更简洁，但理解门槛高一些：

ListNode* reverseListRecursive(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = reverseListRecursive(head->next); head->next->next = head; // 让下一个节点指回当前节点 head->next = nullptr; // 断开当前节点向后的指针 return newHead; }

递归的终止条件是链表为空或只剩下一个节点，这时天然是反转后的状态。递归的核心在于head->next->next = head这一步：假设head->next后面的子链表已经反转过，那head->next现在是子链表的“尾节点”，让这个尾节点指回head，就等于把head接到了子链表的尾部。

递归版虽然代码短，但初次接触时强烈建议配合栈的调用过程去理解，否则面试时手写容易卡壳。我个人在实战中优先用迭代法，因为递归深了可能爆栈，而且迭代法空间复杂度是O(1)，递归是O(n)。

3.3 反转前N个节点和一个区间

链表题里还有一种变形：不是反转整个链表，而是反转前N个，或者反转区间[m, n]。这个如果你只背反转整个链表的模板，很容易懵。

反转前N个节点，关键区别在于：原来反转完整链表时我们最后让head->next = nullptr，但反转前N个，head（也就是反转后的尾节点）要接上第N+1个节点。所以需要额外记录一个successor节点：

ListNode* successor = nullptr; ListNode* reverseN(ListNode* head, int n) { if (n == 1) { successor = head->next; // 记录第 n+1 个节点 return head; } ListNode* newHead = reverseN(head->next, n - 1); head->next->next = head; head->next = successor; // 指向后面的节点，而不是 nullptr return newHead; }

反转区间[m, n]就更进一步：如果m == 1，就是上面的reverseN；如果m > 1，就递归往前推进，直到头节点变成区间起点：

ListNode* reverseBetween(ListNode* head, int m, int n) { if (m == 1) { return reverseN(head, n); } head->next = reverseBetween(head->next, m - 1, n - 1); return head; }

这个写法是我见过的最优雅的递归区间反转。理解它的关键还是那句“前驱节点的next要指向翻转后的头”。如果迭代做区间反转，思路就变成：先走到第m-1个节点，然后从m到n逐个将节点“头插”到m-1后面。两种方法都可以，但我个人觉得递归在这种题里更不容易把指针绕晕。

4. 经典链表算法题：快慢指针、合并与排序

4.1 快慢指针：找中间节点与判断环形链表

快慢指针是链表题的黄金技巧，没有之一。它的原理很朴素：一个指针每次走一步，另一个指针每次走两步。当快指针到达链表末尾时，慢指针恰好走到中间。

ListNode* findMiddleNode(ListNode* head) { if (head == nullptr) return nullptr; ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; }

这个返回的是“右中位数”——如果链表有偶数个节点，它返回的是第n/2+1个节点。如果你想要左中位数，可以调整初始值或循环条件，具体看题目要求。

为什么用这个找中间节点重要？因为它能把链表从中间断开，这样很多“递归合并”“判断回文”的题目就迎刃而解了。比如回文链表判断的经典做法就是：先用快慢指针找到中间节点，反转后半部分，然后逐个比较。

判断环形链表同样用快慢指针：

bool hasCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; }

为什么快慢指针在环形链表里一定会相遇？很简单：一旦两个指针都进入环，快指针每次比慢指针多走一步，相当于在环里每次“追近”一个节点的距离。环的长度是有限的，所以追赶必然成功。这和操场上跑得快的人迟早追上跑得慢的人是一个道理。

这里还有一个经常被追问的进阶版：如果链表有环，如何找到入环点？解法也很经典：当快慢指针相遇后，让慢指针回到头节点，两个指针同时每次走一步，再次相遇的位置就是入环点。这个结论的推导涉及一点数学，但很优美，建议自己去推一遍。

4.2 合并两个有序链表

合并两个有序链表是递归思想在链表里最经典的体现之一。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == nullptr) return l2; if (l2 == nullptr) return l1; if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } }

这个递归的优雅之处在于：它根本不用考虑“当前谁是谁的前驱”，只需要确定“小的那个节点应该接上后面合并好的链表”。每个递归层只返回当前较小的节点作为新链表的头。

如果你想用迭代做，那就得引入虚拟头结点：

ListNode* mergeTwoListsIterative(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = (l1 != nullptr) ? l1 : l2; return dummy->next; }

迭代版的cur->next = (l1 != nullptr) ? l1 : l2;这行是收尾工作：把剩余没比完的链表直接接上。这个操作很多人会忘记，导致合并后的链表后半段凭空消失。写完后建议自己检查一下：两个链表长度不相等时，长的部分有没有被漏掉。

4.3 链表的归并排序：O(n log n)时间、O(1)空间

链表的排序，首选归并排序。原因很直接：链表的物理结构决定了它不适合快速排序里的“随机访问”和“从后往前扫描”；而归并排序只依赖“从前向后”的遍历，天然适配链表。而且在空间上，数组归并排序需要额外O(n)的辅助数组，链表归并排序只需要O(1)的额外空间（递归栈除外）。

核心步骤就三步：找中点、递归排序两半、合并两个有序链表。

ListNode* sortList(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } // 1. 找中点 ListNode* slow = head; ListNode* fast = head; ListNode* prev = nullptr; while (fast != nullptr && fast->next != nullptr) { prev = slow; slow = slow->next; fast = fast->next->next; } prev->next = nullptr; // 断开为两段 // 2. 递归排序两半 ListNode* left = sortList(head); ListNode* right = sortList(slow); // 3. 合并 return mergeTwoLists(left, right); }

注意这里找中点和前面略有不同：需要额外用一个prev记录中点的前一个节点，然后把它和后面断开。如果忘了断开，递归时链表还是完整的一条，结果就是死循环——递归永远切不到单节点。

这个排序是面试链表时的常客，建议多写几遍，直到能一次性通过。链表的mergeTwoLists我们可以直接复用上一节的代码。

4.4 环形链表II：找到入环点

之前提到过入环点的问题，这里直接给出完整推导和代码。

ListNode* detectCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { // 相遇了，说明有环 slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } } return nullptr; }

为什么第二次相遇时就是入环点？假设从链表头到入环点的距离是a，入环点顺时针到第一次相遇点的距离是b，环的剩余长度是c。第一次相遇时，快指针走了a + n(b+c) + b，慢指针走了a + b。因为快指针速度是慢指针的两倍，所以2(a+b) = a + n(b+c) + b，化简得a = (n-1)(b+c) + c。也就是说，从头节点到入环点的距离，等于从相遇点继续走c再加上若干圈环。所以让一个指针从头开始，一个从相遇点开始，每次都走一步，必然在入环点相遇。

这个推导建议自己推一遍，面试时如果直接背结论，被追问“为什么”容易卡壳。

5. 链表删除操作：虚拟头结点的经典场景

5.1 删除指定节点

ListNode* deleteNode(ListNode* head, int val) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* cur = dummy; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* toDelete = cur->next; cur->next = cur->next->next; delete toDelete; return dummy->next; // 只删第一个匹配的节点 } cur = cur->next; } return dummy->next; }

这里用cur->next来判断，是为了在删除时能方便地让前驱的next跨过被删除节点。如果直接用cur判断，删除时还得额外保存前驱，代码反而更长。删除后记得delete，C++不用手动释放内存的语言没这个烦恼，但C++里忘了就是泄漏。

5.2 删除倒数第N个节点

这个题也是经典中的经典。思路：用快慢指针，快指针先走n步，然后快慢指针一起走，当快指针到末尾时，慢指针正好在倒数第n个节点的前一个节点。

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* fast = dummy; ListNode* slow = dummy; // 快指针先走 n+1 步 while (n >= 0 && fast != nullptr) { fast = fast->next; --n; } // 快慢指针一起走 while (fast != nullptr) { fast = fast->next; slow = slow->next; } // 此时 slow 指向倒数第 n+1 个节点 ListNode* toDelete = slow->next; slow->next = slow->next->next; delete toDelete; return dummy->next; }

为什么要让快指针先走n+1步，而不是n步？因为删除倒数第n个节点需要找到它的前驱，也就是倒数第n+1个节点。n+1这个偏移常常让第一次写的人懵，不妨记住：慢指针最后停的位置，就是你确切要操作的节点的前一个。先走n+1步，等快指针到末尾时，慢指针自然就停在了倒数第n+1个节点上。

6. 两个进阶练习：链表的相交与重排

6.1 相交链表：找出两个链表的交点

这个题的优雅解法是双指针交替走：两个指针分别从两个链表头出发，每次走一步，走到末尾后跳到另一个链表的头部继续走。如果两个链表相交，两个指针会在交点相遇；如果不相交，它们会同时走到nullptr。

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA = headA; ListNode* pB = headB; while (pA != pB) { pA = (pA == nullptr) ? headB : pA->next; pB = (pB == nullptr) ? headA : pB->next; } return pA; // 如果没交点，两个指针最终都是 nullptr }

这个解法的时间复杂度是O(m+n)，空间复杂度O(1)，不用额外记录走过的节点。原理也很直观：两个指针走过的总路程相同（分别是m+n和n+m），如果存在交点，它们必然在走过的最后一步之前相遇。

6.2 重排链表：快慢指针+反转+合并

这个题综合了前面好几个技巧，特别适合用来检验自己链表的基本功是否扎实：给定链表1->2->3->4->5，重排成1->5->2->4->3。

思路是三步走：先用快慢指针找到中间节点，把链表拆成前后两段；把后半段反转；然后把后半段交替插入前半段。

void reorderList(ListNode* head) { if (head == nullptr || head->next == nullptr) return; // 第一步：找中间节点 ListNode* slow = head; ListNode* fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } // 此时 slow 是左半段的尾节点 // 第二步：反转后半段 ListNode* secondHead = reverseListIterative(slow->next); slow->next = nullptr; // 断开 // 第三步：交替合并 ListNode* first = head; ListNode* second = secondHead; while (second != nullptr) { ListNode* temp1 = first->next; ListNode* temp2 = second->next; first->next = second; second->next = temp1; first = temp1; second = temp2; } }

注意这里找中间节点时循环条件是fast->next != nullptr && fast->next->next != nullptr，这会让奇数长度时slow停在正中间，偶数长度时停在偏左的位置。这样拆出来的左半段长度不少于右半段，交替合并时才不会出现second比first长导致的问题。

这个题我第一次写的时候，因为拆的时候没把slow->next置为nullptr，结果合并时链表出现了环，直接死循环。这种“断链”的坑，在链表题里太常见了，值得时刻警惕。

7. 链表题的调试技巧与C++内存管理

7.1 打印链表：写一个辅助函数

链表调试最大的痛点是看不见内部状态。数组在IDE里可以直接看元素，链表只能靠眼睛逐节点确认。所以我的习惯是第一时间写一个打印函数：

void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { std::cout << cur->val; if (cur->next != nullptr) { std::cout << " -> "; } cur = cur->next; } std::cout << std::endl; }

每次操作完打印一次，配合断点，绝大多数链表bug能在五分钟内定位。注意循环条件用cur != nullptr，才能把最后一个节点也打出来。

7.2 常见错误盘点

见下表：

7.3 内存释放问题

C++里new出来的链表节点不会自动释放。练习时无所谓，但工程上严谨的析构应该写一个销毁函数：

void deleteList(ListNode* head) { while (head != nullptr) { ListNode* next = head->next; delete head; head = next; } }

如果链表有环，这个函数会死循环。所以释放前要先判环。这也是为什么算法题里我建议先用裸指针把逻辑练明白，什么时候该释放、什么时候不该释放（比如节点还挂在别人的链表里），心里要有数。换成智能指针虽然能自动管理，但循环链表这种场景反而更容易踩坑。

7.4 实例调试：一次完整的段错误排查

给你看一个我真实的踩坑过程，也许比背代码更能培养感觉。有一次我在写“删除指定位置的节点”时，写完自信满满去跑测试，结果一运行就段错误。

我排查的步骤是：先打印一下链表，确认链表本身没问题；然后二分定位，在删除函数的入口、循环体内部各打一个日志；很快就发现循环里第一次访问cur->next->next时，cur->next已经是nullptr了，等于在访问nullptr->next，自然崩溃。根因是循环的终止条件写错了——我在删除节点后没有及时更新循环判断，导致越界访问。

这种问题看代码很难看出来，但打印日志的方式可以秒定位。所以别觉得自己“应该能看出来”就不打印，日志是链表调试最好的朋友。

8. 从练习到工程：链表的性能边界与场景选择

最后聊聊工程视角下的链表。虽然算法题里链表很重要，但在真实的生产代码里，链表的出场率其实没想象中高。原因在于：

• 链表的内存访问是跳跃式的，CPU缓存命中率远低于连续内存的vector，所以即使时间复杂度一样，实际性能也可能差出数倍。
• 链表每个节点都要额外存储一个指针，内存开销大；
• 节点分散在堆上，频繁插入删除时内存分配器压力大。

所以工程里如果你需要频繁在中间插入、删除，且节点数量很大，更常见的做法是用std::deque、std::list（这本身就是双向链表）或者引入“块状链表”“跳表”这些结构来兼顾性能。

但这不代表链表白学了。链表的练习真正锻炼的是三件事：指针操作的严谨性、边界条件的敏感度、递归和迭代两种思维的无缝切换。这些能力在写操作系统代码、实现数据库存储引擎、设计缓存淘汰策略时，都会有直接的回报。也就是说，链表题不只是为了考试，它是在帮你建立操纵内存的直觉。

我自己练链表时有个习惯：不管多简单的题，拿到以后先画图，再写代码，最后用三五个边界用例验证（空链表、单节点、双节点、头尾操作）。这套流程写熟了，后面碰到的很多复杂数据结构题目，都会轻松不少。

如果你现在正处于“链表题看不懂、写不对”的阶段，先别急着跳题，把这篇里的代码一个个敲下来，跑通，再试着改条件看输出变化。链表这关过去了，后面很多路就顺了。