LeetCode - 148. 排序链表
目录
题目
思路
基本情况检查
复杂度分析
执行示例
读者可能出的错误
正确的写法
题目
148. 排序链表 - 力扣（LeetCode）
思路
链表归并排序采用\"分治\"的策略，主要分为三个步骤：
- 分割：将链表从中间分成两个子链表
- 排序：递归地对两个子链表进行排序
- 合并：将两个已排序的子链表合并为一个有序链表
基本情况检查
if (!head || !head->next) return head;- 如果链表为空或只有一个节点，已经是有序的，直接返回
找到链表中点
ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) { slow = slow->next; fast = fast->next->next;}- 使用快慢指针法找到链表中点
- slow指针每次移动一步，fast指针每次移动两步
- 当fast到达链表末尾时，slow指向链表的中间位置（偶数长度链表时指向前半部分的最后一个节点）
分割链表
ListNode* mid = slow->next;slow->next = nullptr;- mid指向后半部分的第一个节点
- 将slow->next设为nullptr，切断链表，得到两个独立的子链表
递归排序
ListNode* left = sortList(head);ListNode* right = sortList(mid);- 递归地对前半部分和后半部分分别进行排序
- 递归将继续分割链表直到子链表长度为1
合并有序链表
return merge(left, right);- 将两个已排序的子链表合并成一个有序链表
合并函数实现
ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* curr = &dummy; while (l1 && l2) { if (l1->val val) { curr->next = l1; l1 = l1->next; } else { curr->next = l2; l2 = l2->next; } curr = curr->next; } curr->next = l1 ? l1 : l2; return dummy.next;}- 创建一个虚拟头节点dummy简化边界情况处理
- 逐个比较两个链表的节点，将较小的节点连接到结果链表
- 当一个链表为空时，将另一个链表的剩余部分直接连接到结果链表
执行示例
复杂度分析
时间复杂度：O(n log n)
- 分割链表：每次将链表分成两半，需要O(log n)次分割
- 每层合并操作：需要O(n)时间
总体时间复杂度：O(n log n)
- 空间复杂度：O(log n)
- 由于递归调用栈的深度为O(log n)
读者可能出的错误写法
class Solution {public: ListNode* sortList(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while(head->next) { slow = slow->next; fast = fast->next->next; } ListNode* mid = slow; slow->next = nullptr; ListNode* left = sortList(head); ListNode* right = sortList(mid); return merge(head,mid); }private: ListNode* merge(ListNode* l1,ListNode*l2) { ListNode* dummy = new ListNode(0); ListNode* current = dummy; while(l1 && l2) { if(l1->val val) { current->next = l1; l1=l1->next; } else { current->next = l2; l2=l2->next; } } while(l1||l2) { if(l1) { current->next = l1; } if(l2) { current->next = l2; } } return dummy; }};无终止条件：缺少递归的基本情况检查，如果head为空或只有一个节点，应该直接返回
快慢指针初始化问题：你的fast和slow都从head开始，但标准做法是slow从head开始，fast从head->next开始
无效的循环条件：你的循环条件是while(head->next)，这不会移动，会导致无限循环。应该是while(fast && fast->next)
链表分割问题：
- 当链表长度为2时，slow和mid会指向同一个节点，导致无限递归
- 应该让mid = slow->next，然后将slow->next = nullptr来正确分割链表
错误的递归参数：在递归调用时，你返回的是merge(head, mid)，但应该是merge(left, right)
merge函数中的问题：
在处理剩余节点时，你的循环条件是while(l1||l2)，但在循环体内没有更新current指针，会导致无限循环
你没有正确处理一个链表为空的情况
内存泄漏：创建了dummy节点但没有释放，应该返回dummy->next并释放dummy
正确的写法
class Solution {public: ListNode* sortList(ListNode* head) { // 基本情况：空链表或只有一个节点 if (!head || !head->next) { return head; } // 1. 使用快慢指针找到链表中点 ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; // 慢指针每次移动一步 fast = fast->next->next; // 快指针每次移动两步 } // 此时slow指向中间节点的前一个节点 ListNode* mid = slow->next; // mid是后半部分的起始节点 slow->next = nullptr; // 断开链表 // 2. 递归排序两个子链表 ListNode* left = sortList(head); // 排序前半部分 ListNode* right = sortList(mid); // 排序后半部分 // 3. 合并两个有序链表 return merge(left, right); } private: // 合并两个有序链表 ListNode* merge(ListNode* l1, ListNode* l2) { // 创建虚拟头节点，简化边界情况处理 ListNode dummy(0); ListNode* curr = &dummy; // 比较两个链表的节点值，将较小的节点添加到结果链表 while (l1 && l2) { if (l1->val val) { curr->next = l1; l1 = l1->next; } else { curr->next = l2; l2 = l2->next; } curr = curr->next; } // 连接剩余部分（如果有） curr->next = l1 ? l1 : l2; return dummy.next; }};
