写在前面承接上篇的三道基石题最近继续刷了四道链表与数组的高频题从数组原地合并到链表反转、归并、分割核心都围绕双指针思想展开但每道题都踩了实打实的坑。这篇把我的最终写法、踩过的真实坑点、以及其他可行思路一起整理出来既是个人复盘也做思路拓展。上篇回顾单链表专题应用篇三道经典题吃透删除、反转与快慢指针本文章代码仓库位置具体说明和使用方法在模块六仓库说明Code_2026: 哈喽欢迎来到我的小天地 这个仓库于2026年8月创建将陪伴我度过大二时期告别前期代码仓库的混乱这里将会记录并分享这一阶段的代码感谢大家支持 - Gitee.com一、合并两个有序数组LeetCode 88题目描述给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意nums1的初始长度为mn前m个是有效元素后n个为0占位最终结果直接存放在nums1中不需要返回值。示例输入nums1 [1,2,3,0,0,0], m3 , nums2 [2,5,6] ,n 3输出[1,2,2,3,5,6]题意分析这道题本质是数组版的归并排序合并步骤但约束很明确必须原地合并不能开额外结果数组。 最开始我本能照搬链表归并的思路想从前向后双指针遍历很快就发现问题nums1前面的有效元素会被写入的值覆盖数据直接丢失。所以最优解一定是从后往前倒着填利用尾部的空闲空间谁大放谁完全不会影响前面的有效数据。我的写法三指针从后向前归并用三个下标分别指向nums1有效末尾、nums2末尾、nums1整体末尾循环比较取大值写入最后单独处理nums2的剩余元素。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int l1 m - 1; int l2 n - 1; int l3 m n - 1; while((l1 0) (l2 0)) { if(nums1[l1] nums2[l2]) { nums1[l3] nums2[l2]; l3--; l2--; } else { nums1[l3] nums1[l1]; l1--; l3--; } } while (l2 0) { nums1[l3] nums2[l2]; l2--; l3--; } }我踩过的坑思维惯性坑一开始直接套链表归并的“从前向后双指针”写了两行才反应过来数组是连续内存向前写会覆盖未读取的有效数据这也是数组和链表归并最核心的区别。多余操作误区循环结束后还补了一段处理l1剩余的循环写完才反应过来nums1剩下的元素本来就在数组前部本身就在正确位置完全不需要额外移动。边界忽略一开始没特意考虑m0的场景也就是nums1全是占位0、所有元素都要从 nums2迁入幸好第二个while循环天然覆盖了这个情况没有出问题。其他可行思路暴力排序法把nums2的元素全部复制到nums1后半段的空位直接对整个nums1做一次排序。思路零门槛完全不用设计指针逻辑缺点是时间复杂度高属于“想不出最优解时的保底写法”。辅助数组法新开一个长度为mn的临时数组两个指针从前向后正常归并写入最后再整体拷贝回nums1。逻辑和链表归并完全一致最好理解缺点是占用额外空间不符合原地合并的进阶要求。二、反转链表LCR 024题目描述给你单链表的头节点head请你反转链表并返回反转后的链表头节点。提示链表中节点的数目范围是[0, 5000]-5000 Node.val 5000题意分析这是链表题的“基本功天花板”后续很多进阶题都会把反转当作子步骤调用。核心本质就是把每个节点的next指针从指向后继改为指向前驱。我选了最稳妥的迭代双指针写法全程原地修改指针空间复杂度O(1)也没有递归栈溢出的风险。我的写法双指针迭代原地反转用前驱指针和当前指针逐步推进每次修改指向前先保存后继节点避免断链。typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head){ ListNode* pcur head; ListNode* next; ListNode* store NULL; while(pcur ! NULL) { next pcur-next; pcur-next store; store pcur; pcur next; } return store; }我踩过的坑经典断链坑最开始写的时候手快先改了pcur-next再去取下一个节点直接把后半段链表弄丢了遍历当场中断。链表操作铁则改next之前一定先存好后继节点。返回值搞反第一次写完下意识返回了pcur结果直接返回空。循环结束时pcur已经走到了NULLstore才停在原链表最后一个节点也就是反转后的新头。认知误区一开始以为反转要新建节点、拷贝数值后来才明白只需要改指针指向节点本身完全可以复用空间开销直接从O(n)降到O(1)。其他可行思路递归反转法核心思想是“先递归反转后面的子链表再把当前节点接到子链表的尾部”。代码写出来非常精简不需要手动管理多个指针但理解门槛更高链表过长时还会有递归栈溢出的风险。新链表头插法遍历原链表的每个节点每次都把当前节点插到新链表的最头部遍历完成后天然就是反转后的链表。和迭代法本质原理一致只是表述和操作视角不同。三、合并两个有序链表LeetCode 21题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。提示两个链表的节点数目范围是[0, 50]-100 Node.val 100l1和l2均按非递减顺序排列题意分析这就是链表版的归并合并和第88题是同一套思想区别只在于数组操作下标、链表操作指针。我采用的是虚拟头节点尾插法也是个人认为最不容易写错、边界最少的写法。我的写法虚拟头双指针尾插新建一个哨兵节点当临时头游走指针负责尾部拼接两个链表同步遍历谁小接谁最后接上剩余部分。typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { ListNode* head1 list1; ListNode* head2 list2; ListNode* dummy (ListNode*)malloc(sizeof(ListNode)); ListNode* cur dummy; while((head1 ! NULL) (head2 ! NULL)) { if(head1-val head2-val) { cur-next head1; head1 head1-next; } else { cur-next head2; head2 head2-next; } cur cur-next; } cur-next head1 ! NULL ? head1 : head2; ListNode* Res dummy-next; free(dummy); return Res; }我踩过的坑致命低级坑第一次写完返回了cur-next而不是dummy-next。cur到最后已经走到了链表尾部cur-next只是后半段剩余节点前面的所有节点直接全部丢失这个bug排查了很久。记住虚拟头的next才是新链表真正的头。内存困惑纠结过malloc的哨兵要不要free、free后要不要把指针置NULL。刷题场景下不 free也能AC但工程代码必须配对释放至于free后置NULL因为函数马上就要返回、局部变量立刻销毁这里置空属于多余操作没有实际意义。走弯路最开始想新建节点拷贝val来拼接后来发现完全可以直接复用原链表节点只改 next指针不用额外申请业务节点。其他可行思路递归合并法每次比较两个链表的头节点把值更小的作为结果头它的next指向剩下两个链表的递归合并结果。不用虚拟头代码极精简但同样有递归栈开销链表很长时不推荐。无虚拟头直接拼接先单独比较选出新的头节点再用指针向后遍历逐个拼接。省掉了一个哨兵节点的malloc但要单独处理头节点的边界情况代码分支更多反而更容易写错。四、分割链表面试题 02.04题目描述给你一个链表的头节点head和一个特定值x请你对链表进行分隔使得所有小于x的节点都出现在大于或等于x的节点之前。不需要保留每个分区中各节点的初始相对位置。提示链表中节点的数目在范围[0, 200]内-100 Node.val 100-200 x 200题意分析这道题是我踩坑最多的一道从审题到指针操作再到边界处理踩了个遍。核心思路很直观一条链存小于x的节点一条链存大于等于x的节点遍历一遍分组最后把两条链拼起来。我的写法双虚拟头尾插分组两个哨兵分别管理两部分链表尾插法逐个接入节点最后拼接并切断大链表尾部防止成环。typedef struct ListNode ListNode; struct ListNode* partition(struct ListNode* head, int x) { ListNode* dummy_small (ListNode*)malloc(sizeof(ListNode)); ListNode* dummy_large (ListNode*)malloc(sizeof(ListNode)); dummy_small-next NULL; dummy_large-next NULL; ListNode* cur_small dummy_small; ListNode* cur_large dummy_large; ListNode* cur head; while(cur ! NULL) { if(cur-val x) { cur_small-next cur; cur_small cur_small-next; } else { cur_large-next cur; cur_large cur_large-next; } cur cur-next; } cur_large-next NULL; cur_small-next dummy_large-next; ListNode* res dummy_small-next; free(dummy_small); free(dummy_large); return res; }我踩过的坑审题自加需求一开始脑补成“小于x在左、等于x在中间、大于x在右”自己给自己加戏差点写成三条链表分组。实际题目只要求两部分等于x直接归到右边即可。野指针崩溃最早的错误写法是给节点val赋值还写了head1Lis1-next但Lis1-next 从来没赋值过全是内存垃圾值一运行直接崩溃。正确做法是直接接入原节点cur-next 当前节点然后cur后移。链表成环坑一开始漏掉了大链表尾部置NULL。原节点都带着旧的next指针如果最后一个大节点原本指向某个小节点拼接完成后链表会成环判题直接超时、内存超限。初始化隐患malloc出来的哨兵节点next是随机垃圾值虽然代码后续会覆盖写入、侥幸能跑通但本质属于未定义行为。严谨起见一定要手动初始化为NULL。命名混乱坑最开始变量名起成head11、head22、Lis1、Lis2写着写着自己就搞混了哪个是哨兵、哪个是游走指针。改成见名知意的命名后逻辑瞬间清晰了很多。其他可行思路头插法分组遍历到小于x的节点就头插到小链表头部大于等于的头插到大连表头部。优点是不用维护尾指针写完直接得到头节点缺点是会颠倒分区内节点的相对顺序题目不要求保序时可以使用。三段式分割分成小于、等于、大于三条独立链表最后按“小→中→大”的顺序拼接。就是我最开始脑补的“x放中间”的效果属于拓展变种只有题目明确要求时才需要用到。五、刷题感悟与方法论总结1. 思路朴素不代表效率低最开始觉得双虚拟头尾插法思路太直白不够“巧妙”结果提交后击败了100%的用户。原因很现实头插法虽然省了两个哨兵但拼接时要额外遍历一次找尾巴实际常数更大尾插法一遍遍历全部搞定实测运行反而更快。算法不是越花哨越好常数小、边界少、不容易写错的写法就是面试和刷题中的好写法。2. 链表题通用避坑口诀修改next前先存后继防止断链头节点不确定就上虚拟头少处理边界拆分重组链表后尾节点一定要手动置NULL防止成环malloc出来的节点成员不会自动为NULL手动初始化更稳妥3. 审题永远是第一步别像我一样自己给题目加需求“等于x放中间”完全是脑补出来的条件。先把题意抠准、边界看清再动手写代码不然写半天都是无用功。六、仓库说明ProjectName ├─ 题目1 │ ├─ source # 源代码文件夹 │ │ ├─ func.h # 头文件 │ │ ├─ test.c │ │ └─ blog_demo.c │ └─ exe # 编译好的可运行程序文件夹 │ └─ main.exe # Windows可执行程序 ├─ 题目2 │ ├─ source │ │ ├─ func.h │ │ ├─ test.c │ │ └─ blog_demo.c │ └─ exe │ └─ main.exe ├─ 题目3 │ ├─ source │ │ ├─ func.h │ │ ├─ test.c │ │ └─ blog_demo.c │ └─ exe │ └─ main.exe └─ 题目4 ├─ source │ ├─ func.h │ ├─ test.c │ └─ blog_demo.c └─ exe └─ main.exeGitee 仓库Code_2026: 哈喽欢迎来到我的小天地 这个仓库于2026年8月创建将陪伴我度过大二时期告别前期代码仓库的混乱这里将会记录并分享这一阶段的代码感谢大家支持仓库包含 4 道编程题目每题独立文件夹无多余垃圾文件。 每个题目下有两个子文件夹source源码目录func.h头文件存放函数声明、结构体、宏定义test.c程序功能测试文件blog_demo.c博客文章配套演示源码exe编译输出目录main.exeWindows 已编译可执行文件双击直接运行使用方法看博客示例代码题目x/source/blog_demo.c功能测试编译运行test.c直接运行程序exe 目录双击main.exe重编译GCC / Dev‑C / VS 编译源码生成新 exe写在最后这四道题刷下来最大的感受是链表题的核心永远是指针指向的管理套路其实就那几种多踩几次坑、多画几遍指针图慢慢就会建立起直觉。下一篇继续刷快慢指针的进阶题型——环形链表、相交链表、倒数第k个节点把龟兔赛跑算法彻底吃透。