1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
// Runtime: 44 ms, faster than 75.98% of C++ online submissions for Sort List.
// Memory Usage: 14.2 MB, less than 15.00% of C++ online submissions for Sort List.
/**
* 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) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(!head || !(head->next)) return head;
ListNode *dummy=new ListNode(0,head);
//记录链表长度
int len=1;
while(head=head->next)
++len;
//每轮循环对两个相邻的长为i的小链表排序
//每轮for循环i长度翻倍，即每轮for循环中长度为i的小链表都已排好序
for(int i=1;i<len;i*=2){
ListNode *l1=nullptr,*l2=nullptr,*rest=dummy->next,*tail=dummy;
//当剩下链表非空时，继续取小链表并merge
while(rest){
//将剩下的链表分为l1、l2、rest三份
//由于bottom-up，l1和l2都在上一个for循环中已排好序
l1=rest;
l2=move_n(l1,i);
rest=move_n(l2,i);
//将排好序的l1和l2进行merge
auto merged=mergeTwoLists(l1,l2);
//将merged的链表左侧加入大链表
tail->next=merged.first;
//将merged的右侧
tail=merged.second;
}
}
return dummy->next;
}
private:
//从链表中取出前n个节点作为小链表，剩下的作为另一部分
ListNode *move_n(ListNode *head,int n){
//移动指针至分割点
while(--n && head)
head=head->next;
//将剩余部分取出
ListNode *rest=(head)?(head->next):nullptr;
//将头n个节点的尾指针置为nullptr，两个链表分开
if(head) head->next=nullptr;
return rest;
}
//将两个排好序的链表merge，返回merge后的首尾节点指针
pair<ListNode *,ListNode *> mergeTwoLists(ListNode* l1, ListNode* l2) {
//建立dummy节点和添加结果用的tail指针
ListNode *dummy=new ListNode;
ListNode *tail=dummy;
//当两个链表都未走到头时，比较两个节点
while(l1 && l2){
//保证l1节点比l2节点小
if(l1->val > l2->val) swap(l1,l2);
//将更小的节点放入结果链表中，继续走
tail->next=l1;
tail=tail->next;
l1=l1->next;
}
//循环终止时可能有一个链表尾部非空，直接放到结果后面
tail->next=l1?l1:l2;
while(tail->next)
tail=tail->next;
return {dummy->next,tail};
}
};
|
的代码使其返回merge结果的首节点和尾节点（便于bottom-up）