教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载导读本文围绕仓库 9 Algorithms Job Interview/2.1 链表-排序.md 中记录的微软面试题展开——给定单链表头指针在不允许使用临时数组或内存拷贝的前提下按升序排序。文章以归并排序为主线完整继承原文档的题目、结点定义与两道延伸题两链表求交点、链表环入口查找并结合仓库中的数组归并排序源码6 Sort/insert_sort.c、有序链表合并实现2.3 链表-2条.md与快慢指针技巧2 链表.md逐层展开。读完本文你将掌握单链表归并排序的完整 C 实现、链表相交检测与环入口查找的推导过程以及这三类问题的复杂度与面试答题要点。问题原型不借助临时数组给单链表排序微软面试题原文档给出的题目如下Given a head pointer pointing to a linked list, please write a function that sort the list in increasing order. You are not allowed to use temporary array or memory copy.微软面试题约束拆解题目表面上是排序真正的考点是两处硬性限制——不能使用临时数组这意味着把链表拷贝到数组 → 数组排序 → 拷回链表这条路被堵死。数组排序如快速排序、堆排序之所以对链表不适用正是因为链表无法 O(1) 随机访问第 k 个元素。不能使用内存拷贝即不能借助 memcpy 之类的操作把结点内容整块搬移排序必须通过重排 next 指针来完成而非搬动数据。原文档给出的结点定义与函数签名为struct { int data; struct S_Node *next; }Node; Node * sort_link_list_increasing_order (Node *pheader):需要说明的是原文档中的结构体定义省略了结点类型名。更规范的写法可参考仓库中通用的链表结点定义2 链表.mdstruct ListNode { int m_nKey; ListNode* m_pNext; };写成等价的 C 风格定义即为typedef struct Node { int data; struct Node *next; } Node; Node *sort_link_list_increasing_order(Node *pheader);为什么归并排序是这道题的最优选择插入排序 / 选择排序可以在链表上原地进行O(n) 空间、O(1) 额外内存但时间复杂度为 O(n²)数据量大时不可接受快速排序依赖随机访问 pivot 与分区链表上虽然可改造如每次以头结点为 pivot 拆分但常数较大、最坏情况退化明显且需要额外的三个子链表空间实现复杂归并排序天然适合链表——它不需要随机访问只需找中点和按序链接两种操作恰好都是链表的强项时间复杂度稳定为 O(n log n)空间上链表版只需递归栈可做到 O(log n)符合题目不借用临时数组的约束。因此单链表排序的面试标准答案就是单链表归并排序这也是原文档第二个小节单链表归并排序的由来。单链表归并排序分治思想在链表上的落地归并排序是什么原文档以一句啥是归并排序引出该主题。归并排序是典型的分治Divide and Conquer算法分三步走分解Divide把待排序序列从中间一分为二得到左右两个子序列递归求解Conquer分别对左右子序列递归调用归并排序直到子序列只剩一个元素天然有序合并Merge把两条已经有序的子序列按序合并成一条完整的有序序列。仓库 8 Algorithms Analysis/分治算法.md 对分治思想有系统讲解而归并排序正是分治策略最经典的载体。数组版归并排序的仓库参考仓库 6 Sort/insert_sort.c 中给出了完整的数组版归并排序实现是理解合并步骤的绝佳参照// 合并2个有序数组,分配一个临时空间装ab的结果最后将合并结果拷贝到数组A void merge_array(int *a,int size_a,int *b, int size_b){ int *tmp malloc( (size_asize_b)*sizeof(int) ); int i,j,k; ijk0; while(isize_a jsize_b){ tmp[k] (a[i]b[j])?b[j]:a[i]; } while(isize_a){ tmp[k]a[i]; } while(jsize_b){ tmp[k]b[j]; } for (int p 0; p k; p) { a[p] tmp[p]; } free(tmp); } void merge_sort(int *a, int length){ if (length1) { merge_sort(a,length/2); merge_sort(alength/2,length-length/2); merge_array(a,length/2,alength/2,length-length/2); } }注意数组版依赖malloc临时数组存放合并结果——这正对应本题不允许使用临时数组的限制。链表版归并排序不需要任何临时数组因为合并两个有序链表只需重排 next 指针即可完成这也是链表版的核心优势。链表版三件套把数组归并排序移植到链表上需要解决三个子问题恰好每一件都能在仓库中找到对应素材找链表的中点用快慢指针。仓库 2 链表.md 明确指出「使用快慢指针的技巧慢指针 slow 前进一步快指针 fast 就前进两步这样当 fast 走到链表末尾时slow 就指向了链表中点」。合并两条有序链表仓库 2.3 链表-2条.md 给出了mergeTwoLists的标准写法——虚拟头结点dummy 双指针逐一比较将值较小的结点接到结果链表尾部。递归分割找到中点后把链表从中点处断开成两条分别递归排序最后合并。完整 C 代码实现综合上述三件套给出可直接编译运行的单链表归并排序#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 合并两条有序链表参照 2.3 链表-2条.md 的 mergeTwoListsC 语言实现 Node *merge_two_lists(Node *l1, Node *l2) { Node dummy {0, NULL}; // 虚拟头结点 Node *p dummy; Node *p1 l1, *p2 l2; while (p1 ! NULL p2 ! NULL) { // 每次把值较小的结点接到 p 指针上 if (p1-data p2-data) { p-next p2; p2 p2-next; } else { p-next p1; p1 p1-next; } p p-next; } // 剩余部分直接接上 p-next (p1 ! NULL) ? p1 : p2; return dummy.next; } // 单链表归并排序升序 Node *sort_link_list_increasing_order(Node *head) { if (head NULL || head-next NULL) return head; // 空链表或单结点天然有序 // 1) 快慢指针找中点fast 到末尾时 slow 恰好在中点前 Node *slow head, *fast head-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } Node *right slow-next; // 右半段起点 slow-next NULL; // 从中点断开得到左右两条链表 // 2) 递归排序左右两半 Node *left_sorted sort_link_list_increasing_order(head); Node *right_sorted sort_link_list_increasing_order(right); // 3) 合并两条有序链表 return merge_two_lists(left_sorted, right_sorted); }要点说明快慢指针的初始化slow head, fast head-next保证了偶数长度时 slow 停在前半段的最后一个结点随后slow-next NULL即可干净地把链表切成两半合并阶段全程只修改next指针、不搬动data完全满足不允许内存拷贝的约束递归基为空链表或单结点此时直接返回天然有序。复杂度分析指标值说明时间复杂度O(n log n)每层归并需要 O(n) 的指针重排共 log n 层空间复杂度O(log n)仅递归调用栈若改用自底向上的迭代归并可做到 O(1) 额外空间稳定性稳定合并时遇到相等元素优先取左链不破坏相对顺序对比数组版归并排序 O(n) 的临时空间见 6 Sort/insert_sort.c 的merge_array中malloc的行为链表版的额外空间开销小得多——这正是它成为链表排序首选方案的根本原因。延伸一两个单链表求第一个交点原文档将链表相交检测作为与链表排序并列的经典题型列出。题目与解法完整继承如下给定两个单链表(head1, head2)检测两个链表是否有交点如果有返回第一个交点。原文档给出的两步解法特判如果head1 head2那么显然相交直接返回head1长度对齐 同步前进分别从head1、head2开始遍历两个链表获得其长度len1与len2假设len1 len2那么指针p1由head1开始向后移动len1 - len2步指针p2 head2下面p1、p2每次向后前进一步并比较p1、p2是否相等如果相等即返回该结点否则说明两个链表没有交点。C 语言实现如下// 返回两个单链表第一个交点无交点返回 NULL Node *first_intersection(Node *head1, Node *head2) { if (head1 head2) return head1; int len1 0, len2 0; for (Node *p head1; p ! NULL; p p-next) len1; for (Node *p head2; p ! NULL; p p-next) len2; Node *p1 head1, *p2 head2; int diff len1 - len2; if (diff 0) { // 让 p1 始终指向较长的链表 Node *t p1; p1 p2; p2 t; diff -diff; } while (diff-- 0) p1 p1-next; // 长链表先走 diff 步 while (p1 ! NULL p1 ! p2) { // 同步前进第一次相等即交点 p1 p1-next; p2 p2-next; } return p1; }复杂度时间 O(len1 len2)空间 O(1)。补充仓库 2.3 链表-2条.md 还记录了该题的进阶版——让 p1 遍历完链表 A 之后开始遍历链表 B让 p2 遍历完链表 B 之后开始遍历链表 A相当于逻辑上把两条链表首尾相接一遍遍历即可求出交点同样 O(1) 空间可作为面试加分项。延伸二单链表环入口查找原文档的第二个延伸题给定单链表(head)如果有环的话请返回从头结点进入环的第一个节点。原文档给出的思路为运用题一我们可以检查链表中是否有环。如果有环那么 p1、p2 重合点 p 必然在环中。从 p 点断开环方法为p1 p, p2 p-next, p-next NULL。此时原单链表可以看作两条单链表一条从 head 开始另一条从 p2 开始于是运用题二的方法我们找到它们的第一个交点即为所求。这里需要澄清原文档中的一处指代笔误检查链表中是否有环靠的是快慢指针仓库 2 链表.md 明确记载p1 每次前进一步p2 每次前进两步。如果 p2 到达链表尾部说明无环否则 p1、p2 必然会在某个时刻相遇而断开环之后求两条链表交点用的才是题一两链表求交点的方法。完整逻辑链条应为快慢指针找相遇点p1 每次走一步、p2 每次走两步若 p2 到达 NULL 说明无环若 p1、p2 相遇于 p则 p 必然在环内从相遇点断开环令tail2 p-next再令p-next NULL。此时环被切断原链表被拆成两条链表——一条从head开始一条从tail2开始套用题一求交点两条链表的第一个交点就是原链表的环入口结点因为从环入口到相遇点 p 这一段是两条链表共享的后缀。C 语言实现复用上面的first_intersection// 返回环入口结点无环返回 NULL Node *cycle_entry(Node *head) { // 1) 快慢指针找相遇点同时完成有环检测 Node *p1 head, *p2 head; while (p2 ! NULL p2-next ! NULL) { p1 p1-next; p2 p2-next-next; if (p1 p2) { // 相遇点 p 必然在环中 // 2) 从相遇点断开环 Node *tail2 p1-next; // 第二条链表的起点 p1-next NULL; // 3) 求 head 与 tail2 两条链表的第一个交点即环入口 return first_intersection(head, tail2); } } return NULL; // 无环 }备选方案Floyd 判环第二段更常见的面试写法是——相遇后令 p1 回到head然后 p1、p2 各自每次走一步二者第一次相遇的结点即为环入口。两种方案结论一致本题记录的是断开环 两链表求交点的转化式思路妙在把新问题归约成已解决的问题值得在面试中讲清这层推导关系。复杂度时间 O(n)空间 O(1)。面试要点与复杂度速查题目核心技巧时间复杂度空间复杂度单链表升序排序微软题归并排序快慢指针找中点 有序链表合并O(n log n)O(log n)递归栈两个链表求第一个交点长度对齐长链先走 diff 步再同步前进O(len1 len2)O(1)链表环入口查找快慢指针找相遇点 → 断开环 → 两链表求交点O(n)O(1)答题时的三个得分点先说清为什么不能用数组题目禁止临时数组与内存拷贝直接排除复制到数组再排序的路径顺势引出指针重排的归并排序讲透归并排序的三步分解快慢指针找中点、递归排序、合并dummy 头结点 双指针并主动说明 O(n log n) 时间与 O(log n) 空间体现归约思维环入口问题通过断开环转化为已解决的两链表求交点问题这类转化思想在面试中非常加分。仓库内延伸阅读9 Algorithms Job Interview/2.1 链表-排序.md本文主文档收录题目原文与延伸题9 Algorithms Job Interview/2 链表.md链表结点定义、双指针/快慢指针通用技巧、环检测、反转、复杂链表复制等基础题9 Algorithms Job Interview/2.3 链表-2条.md两条/多条有序链表的合并含最小堆合并 k 条链表与相交检测的进阶解法9 Algorithms Job Interview/2.2 链表-删除.mdO(1) 删除链表中 p 结点等删除类问题6 Sort/insert_sort.c数组版归并排序源码可对照理解合并步骤的异同8 Algorithms Analysis/分治算法.md归并排序背后的分治方法论。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐LeetCode-Go 排序专题多路快排、链表归并、桶排序与摆动排序的 Go 解法全解LeetCode Go 排序专题多路快排、链表归并、桶排序与摆动排序的 Go 解法全解 本篇技术指南围绕 LeetCode Go https://link.g示例工程LeetCode 23 题解合并 K 个有序链表分治 归并排序LeetCode 23 题解合并 K 个有序链表分治 归并排序 合并 K 个有序链表是 LeetCode 上公认难度为 hard 的链表题也是本仓库文档教程知识库MAS 激活脚本免费教程一条命令完成 Windows 和 Office 授权MAS 激活脚本免费教程一条命令完成 Windows 和 Office 授权 MASMicrosoft Activation Scripts是开源的 Wi操作系统上一篇CTFNote是什么自托管CTF战队协作神器完整上手指南助你高效备战夺旗赛下一篇Craft Agents 许可与商标解读Apache 2.0下你能做什么不能做什么创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考