单链表的“建立”和“逆置”看起来只是《数据结构》第三章里两个再普通不过的小节但很多人学完之后代码能跑题目会做真到了面试或实际项目里却依然说不清“为什么要先画图”“为什么要用头插法”“为什么逆置能有好几种写法”。这篇文章我想直接把这两个操作放在一起讲。因为它们本质上是一件事的两面建立链表是在确定每个节点从哪里来逆置链表是在改变每个节点的指向到哪里去。把这两步吃透你才算真的摸到了“指针操作”的入门门槛。1. 先搞清楚“建立”这个动作到底在干嘛很多人第一次写链表是从一个很简单的需求开始的给一组数把它们存成一个链表。看起来简单真正动手时会遇到第一个选择你这个新节点是加在尾巴上还是加在头上1.1 尾插法最符合直觉也最容易埋坑尾插法的思路是一路向后把每个新来的节点挂到当前最后一个节点后面。典型的 C 风格结构体定义是这样的typedef struct LNode { int data; struct LNode *next; } LNode;尾插法的核心代码可以写成这样LNode* createByTail(int arr[], int n) { LNode *head NULL, *tail NULL; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; if (head NULL) { head s; } else { tail-next s; } tail s; } return head; }这里有两个细节值得停下来看。第一个是tail指针。如果不维护一个尾指针每次插入新节点都要从头遍历到末尾时间复杂度会变成 O(n²)。用尾指针之后每个节点插入是 O(1)整个建表是 O(n)。第二个是head NULL的判断。很多初学者会先申请一个头结点再从这里开始挂节点。那个叫“带头结点”的写法我们后面会专门说。如果你不带头结点第一插入就必须单独处理因为此时链表还是空的。从工程经验看尾插法最适合“输入数据本身有顺序我需要保持这个顺序”的场景。比如从文件里读一堆记录希望链表里的顺序和文件里一致尾插法就是最直接的选择。1.2 头插法第一次体会“顺序反转”的代价头插法的逻辑刚好反过来每次新来的节点都插在 head 前面成为新的头。LNode* createByHead(int arr[], int n) { LNode *head NULL; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next head; head s; } return head; }这个写法非常短短到很多人背下来就完事却没意识到一件重要的事如果你用头插法输入 1、2、3得到的链表是 3、2、1。为什么因为每个新节点都被塞到了最前面。输入顺序越晚越靠近头部。这是理解链表操作的一个关键里程碑链表的顺序不只是你插入时的数据值顺序而是由你的插入策略决定的。2. 逆置的本质把链接方向转过来“逆置”这个词听起来很像“反转”它要求把链表里的节点顺序完全反过来但不改变节点的数据值也不新建一整条链表。2.1 迭代逆转三指针法最经典的迭代写法是三个指针pre、cur、nextLNode* reverseList(LNode *head) { LNode *pre NULL; LNode *cur head; while (cur ! NULL) { LNode *next cur-next; // 先保存后继 cur-next pre; // 改变指向 pre cur; // 指针前移 cur next; } return pre; }用文字描述这个过程其实就是三句话先存住下一个节点不然一改指向就找不到了。把当前节点的 next 指向它的前驱。三个指针整体往后挪一位。这个“先存后改”的习惯几乎是所有链表修改问题的通用解法。不只是逆置删除节点、交换相邻节点、局部反转全都依赖这个思路。2.2 递归逆转代码短但启动心智门槛高递归写法非常优雅但对很多人来说第一眼是懵的。LNode* reverseRecursive(LNode *head) { if (head NULL || head-next NULL) { return head; } LNode *newHead reverseRecursive(head-next); head-next-next head; head-next NULL; return newHead; }理解这段代码的关键不是去追踪每一层递归的调用栈而是相信一个假设如果递归能把 head-next 起点的后半段链表逆置成功那么 head 这个节点要做的只是让自己变成反转后链表的尾节点。所以head-next-next head的意思是让原来 head 的下一个节点反过来指向 head。递归逆置的空间复杂度是 O(n)因为递归调用会占用系统栈。链表很长的时候有栈溢出风险。笔试做题可以用真实项目或者嵌入式环境里我更建议用迭代写法。2.3 为什么头插法已经“建表即逆置”这里需要把两个看起来很不一样的操作连起来看。头插法建表的过程其实就是在做逆置你有一个原始输入序列。每来一个新节点你把它放到现有链表的最前面。最终得到的链表顺序和输入顺序完全相反。所以如果题目要求你用头插法建立链表然后输出你其实已经完成了一次“隐式逆置”。很多同学第一次看到这个结论时会愣一下但它揭示了一个更底层的规律链表的顺序不是一个静态属性而是由你插入的位置决定的动态结果。3. 打通这两个操作背后的心智模型3.1 虚拟头结点带来的工程价值不管是建表还是逆置很多人会被“第一个节点要不要特殊处理”这个问题搞得很烦。尤其在做逆置时head 最后会变成尾节点处理不当就会丢链表。虚拟头结点dummy node就是为了解决这个问题出现的。以尾插法为例如果允许使用虚拟头结点代码可以写成这样LNode* createByTailDummy(int arr[], int n) { LNode dummy; dummy.next NULL; LNode *tail dummy; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; tail-next s; tail s; } return dummy.next; }好处是循环里不再需要判断head NULL了。虚拟头结点永远存在你只需要操作tail-next。逆置时也可以用虚拟头结点思路新建一个空链表然后遍历老链表每拿到一个节点就执行一次“头插”。这种写法本质是把“逆置”转换成了“建表头插”思维负担会小很多。LNode* reverseByDummy(LNode *head) { LNode dummy; dummy.next NULL; LNode *cur head; while (cur ! NULL) { LNode *next cur-next; cur-next dummy.next; dummy.next cur; cur next; } return dummy.next; }这个版本的逆置核心思想是“先把旧链表拆成一个一个节点再用头插法重新组装”。它不需要三指针里的 pre 和 next 同时维护代码量少也更不容易写错。工程上很多复杂的链表操作比如按区间反转、按 K 个一组反转都会用到虚拟头结点。这个技巧值得提前掌握而不是等到刷题时才临时学。3.2 边界条件与典型错误有一类错误几乎所有初学链表的人都会犯。边界的判断是这类操作里最高的隐性成本绝不是代码里少写一个条件那么简单。我个人认为链条最容易断的地方主要集中在这三处空链表逆置一个空链表正确结果应该是空。很多迭代写法里能天然处理while (cur ! NULL)根本不进循环直接返回 pre而 pre 是 NULL。但如果你在代码开头没想清楚这一点很容易写成返回 head结果一看是空没问题再写一个别的函数返回 pre也很容易混。只有一个节点逆置一个只有一个节点的链表结果应该还是这个节点。递归写法里if (head NULL || head-next NULL) return head;直接覆盖了这种情况。迭代写法里循环执行一次后pre 指向原 headcur 变成 NULL逻辑自然正确。指针丢失最经典的错误是把cur-next pre写在了next cur-next之前。// 错误示例 cur-next pre; LNode *next cur-next; // 此时 next 指向 pre已经不是原来的后继了这个问题几乎每个学链表的人都踩过。调试的时候很难发现因为数据量小的时候它可能碰巧还能输出正确结果。调试建议单链表的每一步修改都先问自己一句话——“我改这个指针之前有没有保存它原来的值”哪怕代码再简单也要养成这个习惯。4. 做题、考试与工程应用中的正确打开方式4.1 判断一道链表题到底是“重建”还是“逆置”很多人把“逆置”和“重建”混为一谈。实际上不少链表题目表面上是逆置底子是重建也有题目看起来像重建实际是在逆置。判断标准其实很简单如果题目允许你新建节点、复制数据那是重建。如果题目要求原地修改不能新建节点那才是真正的逆置。比如常见的“判断一个链表是不是回文链表”你当然可以把链表复制一份然后逆置再比较。但更优的做法是找到中点把后半段逆置然后前半段和后半段同时遍历比较。这个做法不需要新建节点是原地逆置。两种思路没有绝对高低但你要能分辨题目考的是哪一种。考试里如果题目写着“空间复杂度 O(1)”你就不能用递归逆置或重建链表。4.2 从“会写”到“会画”再到“会讲”链表题的面试评价标准往往不是代码能不能跑而是你能否把过程画清楚。逆置链表这种题不画图直接写代码出错率极高。哪怕你心里清楚了也要在纸上先画出三个节点的状态变化初始: 1 - 2 - 3 - NULL | | pre cur 第一步: 1 - NULL 2 - 3 - NULL | | pre cur多画两步你会发现 next 指针其实一直保存着那条还没处理完的历史链表。你做的每一步都是“从旧链表上拆一个节点下来挂到新链表上”。平时练习时我建议按这个顺序训练先会画图。再会对着图写代码。然后尝试不看图写代码。最后能做到讲给别人听。这套顺序也适用于任何链表章节的题目不只局限在逆置。4.3 工程里真正会用到的往往是“局部逆置”和“按组逆置”如果只为了考试理解整条链表逆置就够了。但在工程场景里更多时候遇到的是局部逆置。比如业务里有这么一种需求一个消息队列的数据结构是单向链表现在要调整某一段消息的优先级顺序把索引从 m 到 n 的这一段反转其余部分保持原样。这时候你需要的是一个更通用的函数reverseBetween(head, m, n)。思路是先找到第 m-1 个节点它是反转区间的前驱。从这里开始把接下来的 n-m1 个节点逐个头插到前驱后面。最后再接上原来的后继。这种题目刷多了就会发现所有链表操作都在反复使用两个基础能力定位节点和修改链接结构。如果你已经能熟练手写整条链表的逆置再做局部逆置只是多了两步定位工作。学习路径可以很清晰先掌握普通逆置再学带虚拟头结点的局部逆置最后再看 K 个一组反转。把 K 个一组反转的原理想透之后你会发现自己对链表的心智模型完全不一样了。从前你把链表看成“一串节点”现在你会把它看成“一段一段可以重新拼装的序列”。这个转变可能比多刷一百道题更有价值。回到开头那个困惑为什么“单链表的建立”和“逆置”要放在同一个小节里讲因为它们共同提供了通向链表本质的钥匙。建表告诉你顺序怎么形成逆置告诉你怎么把已经形成的顺序改掉建表里那头插法天然逆序的发现会让你在理解逆置时少走很多弯路。从此你面对的不再是一堆next指向和 malloc而是一个你可以控制的线性结构。如果你现在正处于学链表很痛苦的阶段我的建议只有一个不要背代码。先把尾插法、头插法、迭代逆置这三段代码自己在编译器里各完整写三遍。每写一遍都画一次图。画完三遍你大概率会发现链表的难点已经从前面的“看不见摸不着”变成了一条清晰的逻辑链。剩下的只是熟能生巧。
单链表建立与逆置全解析：从头插法到迭代逆转的工程实践
单链表的“建立”和“逆置”看起来只是《数据结构》第三章里两个再普通不过的小节但很多人学完之后代码能跑题目会做真到了面试或实际项目里却依然说不清“为什么要先画图”“为什么要用头插法”“为什么逆置能有好几种写法”。这篇文章我想直接把这两个操作放在一起讲。因为它们本质上是一件事的两面建立链表是在确定每个节点从哪里来逆置链表是在改变每个节点的指向到哪里去。把这两步吃透你才算真的摸到了“指针操作”的入门门槛。1. 先搞清楚“建立”这个动作到底在干嘛很多人第一次写链表是从一个很简单的需求开始的给一组数把它们存成一个链表。看起来简单真正动手时会遇到第一个选择你这个新节点是加在尾巴上还是加在头上1.1 尾插法最符合直觉也最容易埋坑尾插法的思路是一路向后把每个新来的节点挂到当前最后一个节点后面。典型的 C 风格结构体定义是这样的typedef struct LNode { int data; struct LNode *next; } LNode;尾插法的核心代码可以写成这样LNode* createByTail(int arr[], int n) { LNode *head NULL, *tail NULL; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; if (head NULL) { head s; } else { tail-next s; } tail s; } return head; }这里有两个细节值得停下来看。第一个是tail指针。如果不维护一个尾指针每次插入新节点都要从头遍历到末尾时间复杂度会变成 O(n²)。用尾指针之后每个节点插入是 O(1)整个建表是 O(n)。第二个是head NULL的判断。很多初学者会先申请一个头结点再从这里开始挂节点。那个叫“带头结点”的写法我们后面会专门说。如果你不带头结点第一插入就必须单独处理因为此时链表还是空的。从工程经验看尾插法最适合“输入数据本身有顺序我需要保持这个顺序”的场景。比如从文件里读一堆记录希望链表里的顺序和文件里一致尾插法就是最直接的选择。1.2 头插法第一次体会“顺序反转”的代价头插法的逻辑刚好反过来每次新来的节点都插在 head 前面成为新的头。LNode* createByHead(int arr[], int n) { LNode *head NULL; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next head; head s; } return head; }这个写法非常短短到很多人背下来就完事却没意识到一件重要的事如果你用头插法输入 1、2、3得到的链表是 3、2、1。为什么因为每个新节点都被塞到了最前面。输入顺序越晚越靠近头部。这是理解链表操作的一个关键里程碑链表的顺序不只是你插入时的数据值顺序而是由你的插入策略决定的。2. 逆置的本质把链接方向转过来“逆置”这个词听起来很像“反转”它要求把链表里的节点顺序完全反过来但不改变节点的数据值也不新建一整条链表。2.1 迭代逆转三指针法最经典的迭代写法是三个指针pre、cur、nextLNode* reverseList(LNode *head) { LNode *pre NULL; LNode *cur head; while (cur ! NULL) { LNode *next cur-next; // 先保存后继 cur-next pre; // 改变指向 pre cur; // 指针前移 cur next; } return pre; }用文字描述这个过程其实就是三句话先存住下一个节点不然一改指向就找不到了。把当前节点的 next 指向它的前驱。三个指针整体往后挪一位。这个“先存后改”的习惯几乎是所有链表修改问题的通用解法。不只是逆置删除节点、交换相邻节点、局部反转全都依赖这个思路。2.2 递归逆转代码短但启动心智门槛高递归写法非常优雅但对很多人来说第一眼是懵的。LNode* reverseRecursive(LNode *head) { if (head NULL || head-next NULL) { return head; } LNode *newHead reverseRecursive(head-next); head-next-next head; head-next NULL; return newHead; }理解这段代码的关键不是去追踪每一层递归的调用栈而是相信一个假设如果递归能把 head-next 起点的后半段链表逆置成功那么 head 这个节点要做的只是让自己变成反转后链表的尾节点。所以head-next-next head的意思是让原来 head 的下一个节点反过来指向 head。递归逆置的空间复杂度是 O(n)因为递归调用会占用系统栈。链表很长的时候有栈溢出风险。笔试做题可以用真实项目或者嵌入式环境里我更建议用迭代写法。2.3 为什么头插法已经“建表即逆置”这里需要把两个看起来很不一样的操作连起来看。头插法建表的过程其实就是在做逆置你有一个原始输入序列。每来一个新节点你把它放到现有链表的最前面。最终得到的链表顺序和输入顺序完全相反。所以如果题目要求你用头插法建立链表然后输出你其实已经完成了一次“隐式逆置”。很多同学第一次看到这个结论时会愣一下但它揭示了一个更底层的规律链表的顺序不是一个静态属性而是由你插入的位置决定的动态结果。3. 打通这两个操作背后的心智模型3.1 虚拟头结点带来的工程价值不管是建表还是逆置很多人会被“第一个节点要不要特殊处理”这个问题搞得很烦。尤其在做逆置时head 最后会变成尾节点处理不当就会丢链表。虚拟头结点dummy node就是为了解决这个问题出现的。以尾插法为例如果允许使用虚拟头结点代码可以写成这样LNode* createByTailDummy(int arr[], int n) { LNode dummy; dummy.next NULL; LNode *tail dummy; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; tail-next s; tail s; } return dummy.next; }好处是循环里不再需要判断head NULL了。虚拟头结点永远存在你只需要操作tail-next。逆置时也可以用虚拟头结点思路新建一个空链表然后遍历老链表每拿到一个节点就执行一次“头插”。这种写法本质是把“逆置”转换成了“建表头插”思维负担会小很多。LNode* reverseByDummy(LNode *head) { LNode dummy; dummy.next NULL; LNode *cur head; while (cur ! NULL) { LNode *next cur-next; cur-next dummy.next; dummy.next cur; cur next; } return dummy.next; }这个版本的逆置核心思想是“先把旧链表拆成一个一个节点再用头插法重新组装”。它不需要三指针里的 pre 和 next 同时维护代码量少也更不容易写错。工程上很多复杂的链表操作比如按区间反转、按 K 个一组反转都会用到虚拟头结点。这个技巧值得提前掌握而不是等到刷题时才临时学。3.2 边界条件与典型错误有一类错误几乎所有初学链表的人都会犯。边界的判断是这类操作里最高的隐性成本绝不是代码里少写一个条件那么简单。我个人认为链条最容易断的地方主要集中在这三处空链表逆置一个空链表正确结果应该是空。很多迭代写法里能天然处理while (cur ! NULL)根本不进循环直接返回 pre而 pre 是 NULL。但如果你在代码开头没想清楚这一点很容易写成返回 head结果一看是空没问题再写一个别的函数返回 pre也很容易混。只有一个节点逆置一个只有一个节点的链表结果应该还是这个节点。递归写法里if (head NULL || head-next NULL) return head;直接覆盖了这种情况。迭代写法里循环执行一次后pre 指向原 headcur 变成 NULL逻辑自然正确。指针丢失最经典的错误是把cur-next pre写在了next cur-next之前。// 错误示例 cur-next pre; LNode *next cur-next; // 此时 next 指向 pre已经不是原来的后继了这个问题几乎每个学链表的人都踩过。调试的时候很难发现因为数据量小的时候它可能碰巧还能输出正确结果。调试建议单链表的每一步修改都先问自己一句话——“我改这个指针之前有没有保存它原来的值”哪怕代码再简单也要养成这个习惯。4. 做题、考试与工程应用中的正确打开方式4.1 判断一道链表题到底是“重建”还是“逆置”很多人把“逆置”和“重建”混为一谈。实际上不少链表题目表面上是逆置底子是重建也有题目看起来像重建实际是在逆置。判断标准其实很简单如果题目允许你新建节点、复制数据那是重建。如果题目要求原地修改不能新建节点那才是真正的逆置。比如常见的“判断一个链表是不是回文链表”你当然可以把链表复制一份然后逆置再比较。但更优的做法是找到中点把后半段逆置然后前半段和后半段同时遍历比较。这个做法不需要新建节点是原地逆置。两种思路没有绝对高低但你要能分辨题目考的是哪一种。考试里如果题目写着“空间复杂度 O(1)”你就不能用递归逆置或重建链表。4.2 从“会写”到“会画”再到“会讲”链表题的面试评价标准往往不是代码能不能跑而是你能否把过程画清楚。逆置链表这种题不画图直接写代码出错率极高。哪怕你心里清楚了也要在纸上先画出三个节点的状态变化初始: 1 - 2 - 3 - NULL | | pre cur 第一步: 1 - NULL 2 - 3 - NULL | | pre cur多画两步你会发现 next 指针其实一直保存着那条还没处理完的历史链表。你做的每一步都是“从旧链表上拆一个节点下来挂到新链表上”。平时练习时我建议按这个顺序训练先会画图。再会对着图写代码。然后尝试不看图写代码。最后能做到讲给别人听。这套顺序也适用于任何链表章节的题目不只局限在逆置。4.3 工程里真正会用到的往往是“局部逆置”和“按组逆置”如果只为了考试理解整条链表逆置就够了。但在工程场景里更多时候遇到的是局部逆置。比如业务里有这么一种需求一个消息队列的数据结构是单向链表现在要调整某一段消息的优先级顺序把索引从 m 到 n 的这一段反转其余部分保持原样。这时候你需要的是一个更通用的函数reverseBetween(head, m, n)。思路是先找到第 m-1 个节点它是反转区间的前驱。从这里开始把接下来的 n-m1 个节点逐个头插到前驱后面。最后再接上原来的后继。这种题目刷多了就会发现所有链表操作都在反复使用两个基础能力定位节点和修改链接结构。如果你已经能熟练手写整条链表的逆置再做局部逆置只是多了两步定位工作。学习路径可以很清晰先掌握普通逆置再学带虚拟头结点的局部逆置最后再看 K 个一组反转。把 K 个一组反转的原理想透之后你会发现自己对链表的心智模型完全不一样了。从前你把链表看成“一串节点”现在你会把它看成“一段一段可以重新拼装的序列”。这个转变可能比多刷一百道题更有价值。回到开头那个困惑为什么“单链表的建立”和“逆置”要放在同一个小节里讲因为它们共同提供了通向链表本质的钥匙。建表告诉你顺序怎么形成逆置告诉你怎么把已经形成的顺序改掉建表里那头插法天然逆序的发现会让你在理解逆置时少走很多弯路。从此你面对的不再是一堆next指向和 malloc而是一个你可以控制的线性结构。如果你现在正处于学链表很痛苦的阶段我的建议只有一个不要背代码。先把尾插法、头插法、迭代逆置这三段代码自己在编译器里各完整写三遍。每写一遍都画一次图。画完三遍你大概率会发现链表的难点已经从前面的“看不见摸不着”变成了一条清晰的逻辑链。剩下的只是熟能生巧。