企业官网建设流程全解析

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

148.排序链表

2、题目描述

二、个人思路整理

1、思路分析

思路1：自顶向下归并排序（递归法）

具体步骤：

1. 找中点并断开：使用快慢指针（slow走一步，fast走两步，fast初始化为head->next可保证偶数节点时slow落在前半段末尾），将链表一分为二，断开连接（mid = slow->next; slow->next = nullptr;）。
2. 递归排序：分别对左右两半链表递归调用sortList。
3. 合并有序链表：调用经典的合并两个有序链表（双指针 + 虚拟头节点dummy）。

思路2：自底向上归并排序（迭代法）

具体步骤：

1. 求长度：先遍历一次链表得到总长度length。
2. 倍增步长归并：定义子链表长度subLength，从 1 开始，每次翻倍（1, 2, 4, 8...），直到subLength >= length。
3. 分段合并：每次循环中，从头到尾按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*slow=head;ListNode*fast=head->next;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}ListNode*mid=slow->next;slow->next=nullptr;// 必须断开前半段与后半段的连接// 2. 递归对左右两半分别进行排序ListNode*left=sortList(head);ListNode*right=sortList(mid);// 3. 合并两个有序链表returnmerge(left,right);}private:ListNode*merge(ListNode*l1,ListNode*l2){// 使用栈上分配的哨兵节点（dummy head），避免处理头节点为空的特殊边界ListNodedummy(0);ListNode*tail=&dummy;// tail指针始终指向合并后新链表的末尾// 双指针比较：每次将较小值的节点追加到新链表尾部while(l1&&l2){if(l1->val<l2->val){tail->next=l1;l1=l1->next;}else{tail->next=l2;l2=l2->next;}tail=tail->next;// 尾指针后移}// 链表特性：当其中一条遍历完毕，直接将另一条剩余链表整体拼接到末尾，无需循环tail->next=l1?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. 遍历一次链表获取总长度intlength=0;ListNode*node=head;while(node){length++;node=node->next;}// 引入哨兵节点挂载整个链表，便于统一处理头节点的变更ListNodedummy(0,head);// 2. 步长 subLength 从 1 开始翻倍：1 -> 2 -> 4 -> 8 ...for(intsubLength=1;subLength<length;subLength<<=1){ListNode*prev=&dummy;// prev 始终指向上一组已合并完成部分的尾节点ListNode*curr=dummy.next;// curr 指向当前待处理子链表的起始位置while(curr){// 截取第一段长为 subLength 的子链表ListNode*head1=curr;for(inti=1;i<subLength&&curr->next;i++){curr=curr->next;}// 截取第二段长为 subLength 的子链表ListNode*head2=curr->next;curr->next=nullptr;// 断开第一段末尾curr=head2;for(inti=1;i<subLength&&curr&&curr->next;i++){curr=curr->next;}// 记录下一组的起点，并断开第二段末尾ListNode*nextGroup=nullptr;if(curr){nextGroup=curr->next;curr->next=nullptr;// 断开第二段末尾}// 合并 head1 和 head2 两个有序子链表ListNode*merged=merge(head1,head2);prev->next=merged;// 将合并后的结果挂接到前一组的末尾// 移动 prev 到当前合并后链表的尾节点，为下一次拼接做准备while(prev->next){prev=prev->next;}curr=nextGroup;// 移动到下一组子链表起点}}returndummy.next;}private:ListNode*merge(ListNode*l1,ListNode*l2){// 使用栈上分配的哨兵节点（dummy head），避免处理头节点为空的特殊边界ListNodedummy(0);ListNode*tail=&dummy;// tail指针始终指向合并后新链表的末尾// 双指针比较：每次将较小值的节点追加到新链表尾部while(l1&&l2){if(l1->val<l2->val){tail->next=l1;l1=l1->next;}else{tail->next=l2;l2=l2->next;}tail=tail->next;// 尾指针后移}// 链表特性：当其中一条遍历完毕，直接将另一条剩余链表整体拼接到末尾，无需循环tail->next=l1?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每次都要执行，否则新链表无法正确串联。
• 剩余链表拼接：当一条链表遍历完毕，直接将另一条剩余链表整体拼接到末尾，无需循环。
  算法变体与扩展：

1. 合并 K 个升序链表：将两两归并推广到 K 路归并，可用分治或优先队列实现（对应 LeetCode 23）。
2. 数组归并排序：将归并思想应用到数组，借助临时数组完成合并，是经典的O ( n log ⁡ n ) O(n \log n)O(nlogn)排序算法。
3. 链表插入排序：对链表使用插入排序，时间复杂度为O ( n 2 ) O(n^2)O(n2)，适合近乎有序的短链表（对应 LeetCode 147）。
4. 链表快速排序：对链表使用快速排序，平均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. 排序数组（数组归并排序，借助临时数组）