1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9
10 class Solution {
11 public:
12 ListNode* sortList(ListNode*
head) {
13 ListNode dummyHead(
0);
14 dummyHead.next =
head;
15 auto p =
head;
16 int length =
0;
17 while (p) {
18 ++
length;
19 p = p->
next;
20 }
21
22 for (
int size =
1; size < length; size <<=
1) {
23 auto cur =
dummyHead.next;
24 auto tail = &
dummyHead;
25
26 while (cur) {
27 auto left =
cur;
28 auto right = cut(left, size);
// left->@->@ right->@->@->@...
29 cur = cut(right, size);
// left->@->@ right->@->@ cur->@->...
30
31 tail->next =
merge(left, right);
32 while (tail->
next) {
33 tail = tail->
next;
34 }
35 }
36 }
37 return dummyHead.next;
38 }
39
40 ListNode* cut(ListNode* head,
int n) {
41 auto p =
head;
42 while (--n &&
p) {
43 p = p->
next;
44 }
45
46 if (!p)
return nullptr;
47
48 auto next = p->
next;
49 p->next =
nullptr;
50 return next;
51 }
52
53 ListNode* merge(ListNode* l1, ListNode*
l2) {
54 ListNode dummyHead(
0);
55 auto p = &
dummyHead;
56 while (l1 &&
l2) {
57 if (l1->val < l2->
val) {
58 p->next =
l1;
59 p =
l1;
60 l1 = l1->
next;
61 }
else {
62 p->next =
l2;
63 p =
l2;
64 l2 = l2->
next;
65 }
66 }
67 p->next = l1 ?
l1 : l2;
68 return dummyHead.next;
69 }
70 };
由下至上的归并排序
转载于:https://www.cnblogs.com/zhuangbijingdeboke/p/11321922.html
