Sort a linked list in O(n log n) time using constant space complexity.
使用归并排序。
首先需要把链表分成左右两部分，使用快慢指针法找到中间节点
ListNode *slow = head;
ListNode *fast = head,
ListNode *prev = head; // 假设至少2个节点，因此while至少执行一次
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr; // 断开左右部分
此时left = head, right = slow:
ListNode *left = head;
ListNode *right = slow;
分别调用mergeSort对左右部分排序:
left = mergeSort(left);
right = mergeSort(right);
然后合并左右两个部分即可:
ListNode *merged = merge(left, right);
完整代码:
ListNode *mergeSort(ListNode *head) {
if (!head || !head->next) // 少于2个节点直接返回
return head;
ListNode *slow = head;
ListNode *fast = head;
ListNode *prev = head; // 至少2个节点，因此while至少执行一次
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;// 断开左右两部分
ListNode *left = mergeSort(head);
ListNode *right = mergeSort(slow);
ListNode *merged = merge(left, right);
return merged;
}
合并两个链表可以使用迭代法Merge Two Sorted Lists，也可以使用递归法，下面是递归实现方法:
ListNode *merge(ListNode *l1, ListNode *l2) {
if (l1 == nullptr)
return l2;
if (l2 == nullptr)
return l1;
if (l1->val <= l2->val) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
- Merge Two Sorted Lists: 合并两个链表
- Merge k Sorted Lists: 合并K个链表
- Merge Sorted Array: 合并两个数组
- Sort List: 归并排序两个链表