尧图网页设计 
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析思路1自顶向下归并排序递归法思路2自底向上归并排序迭代法2、解题代码思路1自顶向下归并排序递归法思路2自底向上归并排序迭代法三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接148.排序链表2、题目描述二、个人思路整理1、思路分析思路1自顶向下归并排序递归法具体步骤找中点并断开使用快慢指针slow走一步fast走两步fast初始化为head-next可保证偶数节点时slow落在前半段末尾将链表一分为二断开连接mid slow-next; slow-next nullptr;。递归排序分别对左右两半链表递归调用sortList。合并有序链表调用经典的合并两个有序链表双指针 虚拟头节点dummy。思路2自底向上归并排序迭代法具体步骤求长度先遍历一次链表得到总长度length。倍增步长归并定义子链表长度subLength从 1 开始每次翻倍1, 2, 4, 8...直到subLength length。分段合并每次循环中从头到尾按subLength截取两段子链表进行合并并将合并结果接到上一段的尾部。2、解题代码思路1自顶向下归并排序递归法/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*sortList(ListNode*head){// 空链表或只有一个节点时直接返回if(!head||!head-next){returnhead;}// 1. 快慢指针找中点// fast初始化为head-next可以保证链表节点为偶数时slow停在前半段末尾ListNode*slowhead;ListNode*fasthead-next;while(fastfast-next){slowslow-next;fastfast-next-next;}ListNode*midslow-next;slow-nextnullptr;// 必须断开前半段与后半段的连接// 2. 递归对左右两半分别进行排序ListNode*leftsortList(head);ListNode*rightsortList(mid);// 3. 合并两个有序链表returnmerge(left,right);}private:ListNode*merge(ListNode*l1,ListNode*l2){// 使用栈上分配的哨兵节点dummy head避免处理头节点为空的特殊边界ListNodedummy(0);ListNode*taildummy;// tail指针始终指向合并后新链表的末尾// 双指针比较每次将较小值的节点追加到新链表尾部while(l1l2){if(l1-vall2-val){tail-nextl1;l1l1-next;}else{tail-nextl2;l2l2-next;}tailtail-next;// 尾指针后移}// 链表特性当其中一条遍历完毕直接将另一条剩余链表整体拼接到末尾无需循环tail-nextl1?l1:l2;returndummy.next;// 返回合并后的真正头节点}};复杂度分析时间复杂度O ( n log n ) O(n \log n)O(nlogn)每一层递归都会对链表进行一趟完整的遍历与合并耗时O ( n ) O(n)O(n)递归将链表不断对半分割共需log n \log nlogn层两者相乘总时间复杂度为O ( n log n ) O(n \log n)O(nlogn)。空间复杂度O ( log n ) O(\log n)O(logn)递归调用栈的深度为log n \log nlogn每次对半分割。思路2自底向上归并排序迭代法/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*sortList(ListNode*head){// 空链表或只有一个节点时直接返回if(!head||!head-next){returnhead;}// 1. 遍历一次链表获取总长度intlength0;ListNode*nodehead;while(node){length;nodenode-next;}// 引入哨兵节点挂载整个链表便于统一处理头节点的变更ListNodedummy(0,head);// 2. 步长 subLength 从 1 开始翻倍1 - 2 - 4 - 8 ...for(intsubLength1;subLengthlength;subLength1){ListNode*prevdummy;// prev 始终指向上一组已合并完成部分的尾节点ListNode*currdummy.next;// curr 指向当前待处理子链表的起始位置while(curr){// 截取第一段长为 subLength 的子链表ListNode*head1curr;for(inti1;isubLengthcurr-next;i){currcurr-next;}// 截取第二段长为 subLength 的子链表ListNode*head2curr-next;curr-nextnullptr;// 断开第一段末尾currhead2;for(inti1;isubLengthcurrcurr-next;i){currcurr-next;}// 记录下一组的起点并断开第二段末尾ListNode*nextGroupnullptr;if(curr){nextGroupcurr-next;curr-nextnullptr;// 断开第二段末尾}// 合并 head1 和 head2 两个有序子链表ListNode*mergedmerge(head1,head2);prev-nextmerged;// 将合并后的结果挂接到前一组的末尾// 移动 prev 到当前合并后链表的尾节点为下一次拼接做准备while(prev-next){prevprev-next;}currnextGroup;// 移动到下一组子链表起点}}returndummy.next;}private:ListNode*merge(ListNode*l1,ListNode*l2){// 使用栈上分配的哨兵节点dummy head避免处理头节点为空的特殊边界ListNodedummy(0);ListNode*taildummy;// tail指针始终指向合并后新链表的末尾// 双指针比较每次将较小值的节点追加到新链表尾部while(l1l2){if(l1-vall2-val){tail-nextl1;l1l1-next;}else{tail-nextl2;l2l2-next;}tailtail-next;// 尾指针后移}// 链表特性当其中一条遍历完毕直接将另一条剩余链表整体拼接到末尾无需循环tail-nextl1?l1:l2;returndummy.next;// 返回合并后的真正头节点}};复杂度分析时间复杂度O ( n log n ) O(n \log n)O(nlogn)外层循环中步长subLength从 1 开始倍增共执行log n \log nlogn轮每一轮都会从头到尾遍历整条链表进行分段合并耗时O ( n ) O(n)O(n)两者相乘总时间复杂度为O ( n log n ) O(n \log n)O(nlogn)。空间复杂度O ( 1 ) O(1)O(1)常数级个变量空间。三、知识风暴归并排序 链表是本题的核心思想利用归并排序的分治策略配合链表天然的指针操作在O ( n log n ) O(n \log n)O(nlogn)时间内完成链表的原地排序无需额外数组空间。算法核心思想分治思想将链表不断对半分割直到每个子链表只有一个节点天然有序再逐层合并是归并排序的核心。快慢指针找中点slow走一步、fast走两步fast到达末尾时slow恰好位于链表中间实现O ( n ) O(n)O(n)的均匀分割。双指针合并合并两个有序链表时用双指针逐个比较节点值借助哨兵节点dummy简化头节点处理。原地排序全程只修改节点指针、不申请额外数组空间开销仅来自递归栈递归法或常数个指针迭代法。常见对比哈希表法 vs 节点交织法常见对比自顶向下归并 vs 自底向上归并使用要点找中点fast初始化为head-next可保证偶数节点时slow落在前半段末尾分割均匀。断开连接slow-next nullptr必须执行否则左右两半仍相连递归会陷入死循环。哨兵节点合并时使用栈上分配的dummy节点避免处理头节点为空的特殊边界。尾指针后移合并过程中tail tail-next每次都要执行否则新链表无法正确串联。剩余链表拼接当一条链表遍历完毕直接将另一条剩余链表整体拼接到末尾无需循环。算法变体与扩展合并 K 个升序链表将两两归并推广到 K 路归并可用分治或优先队列实现对应 LeetCode 23。数组归并排序将归并思想应用到数组借助临时数组完成合并是经典的O ( n log n ) O(n \log n)O(nlogn)排序算法。链表插入排序对链表使用插入排序时间复杂度为O ( n 2 ) O(n^2)O(n2)适合近乎有序的短链表对应 LeetCode 147。链表快速排序对链表使用快速排序平均O ( n log n ) O(n \log n)O(nlogn)但最坏退化为O ( n 2 ) O(n^2)O(n2)且指针操作更复杂。与其他算法的对比自顶向下归并递归O ( n log n ) O(n \log n)O(nlogn)时间、O ( log n ) O(\log n)O(logn)空间思路直观、代码简洁但递归栈有额外开销链表过长时可能栈溢出。自底向上归并迭代O ( n log n ) O(n \log n)O(nlogn)时间、O ( 1 ) O(1)O(1)空间无递归栈开销空间更优但指针操作更复杂需仔细处理分段与拼接。相关 LeetCode 例题23. 合并 K 个升序链表K 路归并分治或优先队列147. 对链表进行插入排序链表插入排序O ( n 2 ) O(n^2)O(n2)21. 合并两个有序链表归并排序的基础合并操作912. 排序数组数组归并排序借助临时数组 【链表】LC 148.排序链表
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析思路1自顶向下归并排序递归法思路2自底向上归并排序迭代法2、解题代码思路1自顶向下归并排序递归法思路2自底向上归并排序迭代法三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接148.排序链表2、题目描述二、个人思路整理1、思路分析思路1自顶向下归并排序递归法具体步骤找中点并断开使用快慢指针slow走一步fast走两步fast初始化为head-next可保证偶数节点时slow落在前半段末尾将链表一分为二断开连接mid slow-next; slow-next nullptr;。递归排序分别对左右两半链表递归调用sortList。合并有序链表调用经典的合并两个有序链表双指针 虚拟头节点dummy。思路2自底向上归并排序迭代法具体步骤求长度先遍历一次链表得到总长度length。倍增步长归并定义子链表长度subLength从 1 开始每次翻倍1, 2, 4, 8...直到subLength length。分段合并每次循环中从头到尾按subLength截取两段子链表进行合并并将合并结果接到上一段的尾部。2、解题代码思路1自顶向下归并排序递归法/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*sortList(ListNode*head){// 空链表或只有一个节点时直接返回if(!head||!head-next){returnhead;}// 1. 快慢指针找中点// fast初始化为head-next可以保证链表节点为偶数时slow停在前半段末尾ListNode*slowhead;ListNode*fasthead-next;while(fastfast-next){slowslow-next;fastfast-next-next;}ListNode*midslow-next;slow-nextnullptr;// 必须断开前半段与后半段的连接// 2. 递归对左右两半分别进行排序ListNode*leftsortList(head);ListNode*rightsortList(mid);// 3. 合并两个有序链表returnmerge(left,right);}private:ListNode*merge(ListNode*l1,ListNode*l2){// 使用栈上分配的哨兵节点dummy head避免处理头节点为空的特殊边界ListNodedummy(0);ListNode*taildummy;// tail指针始终指向合并后新链表的末尾// 双指针比较每次将较小值的节点追加到新链表尾部while(l1l2){if(l1-vall2-val){tail-nextl1;l1l1-next;}else{tail-nextl2;l2l2-next;}tailtail-next;// 尾指针后移}// 链表特性当其中一条遍历完毕直接将另一条剩余链表整体拼接到末尾无需循环tail-nextl1?l1:l2;returndummy.next;// 返回合并后的真正头节点}};复杂度分析时间复杂度O ( n log n ) O(n \log n)O(nlogn)每一层递归都会对链表进行一趟完整的遍历与合并耗时O ( n ) O(n)O(n)递归将链表不断对半分割共需log n \log nlogn层两者相乘总时间复杂度为O ( n log n ) O(n \log n)O(nlogn)。空间复杂度O ( log n ) O(\log n)O(logn)递归调用栈的深度为log n \log nlogn每次对半分割。思路2自底向上归并排序迭代法/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*sortList(ListNode*head){// 空链表或只有一个节点时直接返回if(!head||!head-next){returnhead;}// 1. 遍历一次链表获取总长度intlength0;ListNode*nodehead;while(node){length;nodenode-next;}// 引入哨兵节点挂载整个链表便于统一处理头节点的变更ListNodedummy(0,head);// 2. 步长 subLength 从 1 开始翻倍1 - 2 - 4 - 8 ...for(intsubLength1;subLengthlength;subLength1){ListNode*prevdummy;// prev 始终指向上一组已合并完成部分的尾节点ListNode*currdummy.next;// curr 指向当前待处理子链表的起始位置while(curr){// 截取第一段长为 subLength 的子链表ListNode*head1curr;for(inti1;isubLengthcurr-next;i){currcurr-next;}// 截取第二段长为 subLength 的子链表ListNode*head2curr-next;curr-nextnullptr;// 断开第一段末尾currhead2;for(inti1;isubLengthcurrcurr-next;i){currcurr-next;}// 记录下一组的起点并断开第二段末尾ListNode*nextGroupnullptr;if(curr){nextGroupcurr-next;curr-nextnullptr;// 断开第二段末尾}// 合并 head1 和 head2 两个有序子链表ListNode*mergedmerge(head1,head2);prev-nextmerged;// 将合并后的结果挂接到前一组的末尾// 移动 prev 到当前合并后链表的尾节点为下一次拼接做准备while(prev-next){prevprev-next;}currnextGroup;// 移动到下一组子链表起点}}returndummy.next;}private:ListNode*merge(ListNode*l1,ListNode*l2){// 使用栈上分配的哨兵节点dummy head避免处理头节点为空的特殊边界ListNodedummy(0);ListNode*taildummy;// tail指针始终指向合并后新链表的末尾// 双指针比较每次将较小值的节点追加到新链表尾部while(l1l2){if(l1-vall2-val){tail-nextl1;l1l1-next;}else{tail-nextl2;l2l2-next;}tailtail-next;// 尾指针后移}// 链表特性当其中一条遍历完毕直接将另一条剩余链表整体拼接到末尾无需循环tail-nextl1?l1:l2;returndummy.next;// 返回合并后的真正头节点}};复杂度分析时间复杂度O ( n log n ) O(n \log n)O(nlogn)外层循环中步长subLength从 1 开始倍增共执行log n \log nlogn轮每一轮都会从头到尾遍历整条链表进行分段合并耗时O ( n ) O(n)O(n)两者相乘总时间复杂度为O ( n log n ) O(n \log n)O(nlogn)。空间复杂度O ( 1 ) O(1)O(1)常数级个变量空间。三、知识风暴归并排序 链表是本题的核心思想利用归并排序的分治策略配合链表天然的指针操作在O ( n log n ) O(n \log n)O(nlogn)时间内完成链表的原地排序无需额外数组空间。算法核心思想分治思想将链表不断对半分割直到每个子链表只有一个节点天然有序再逐层合并是归并排序的核心。快慢指针找中点slow走一步、fast走两步fast到达末尾时slow恰好位于链表中间实现O ( n ) O(n)O(n)的均匀分割。双指针合并合并两个有序链表时用双指针逐个比较节点值借助哨兵节点dummy简化头节点处理。原地排序全程只修改节点指针、不申请额外数组空间开销仅来自递归栈递归法或常数个指针迭代法。常见对比哈希表法 vs 节点交织法常见对比自顶向下归并 vs 自底向上归并使用要点找中点fast初始化为head-next可保证偶数节点时slow落在前半段末尾分割均匀。断开连接slow-next nullptr必须执行否则左右两半仍相连递归会陷入死循环。哨兵节点合并时使用栈上分配的dummy节点避免处理头节点为空的特殊边界。尾指针后移合并过程中tail tail-next每次都要执行否则新链表无法正确串联。剩余链表拼接当一条链表遍历完毕直接将另一条剩余链表整体拼接到末尾无需循环。算法变体与扩展合并 K 个升序链表将两两归并推广到 K 路归并可用分治或优先队列实现对应 LeetCode 23。数组归并排序将归并思想应用到数组借助临时数组完成合并是经典的O ( n log n ) O(n \log n)O(nlogn)排序算法。链表插入排序对链表使用插入排序时间复杂度为O ( n 2 ) O(n^2)O(n2)适合近乎有序的短链表对应 LeetCode 147。链表快速排序对链表使用快速排序平均O ( n log n ) O(n \log n)O(nlogn)但最坏退化为O ( n 2 ) O(n^2)O(n2)且指针操作更复杂。与其他算法的对比自顶向下归并递归O ( n log n ) O(n \log n)O(nlogn)时间、O ( log n ) O(\log n)O(logn)空间思路直观、代码简洁但递归栈有额外开销链表过长时可能栈溢出。自底向上归并迭代O ( n log n ) O(n \log n)O(nlogn)时间、O ( 1 ) O(1)O(1)空间无递归栈开销空间更优但指针操作更复杂需仔细处理分段与拼接。相关 LeetCode 例题23. 合并 K 个升序链表K 路归并分治或优先队列147. 对链表进行插入排序链表插入排序O ( n 2 ) O(n^2)O(n2)21. 合并两个有序链表归并排序的基础合并操作912. 排序数组数组归并排序借助临时数组