LeetCode sort-list

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。 示例 1:

输入: 4->2->1->3 输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0 输出: -1->0->3->4->5

解答:

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
class Solution {
public:
ListNode* sortList(ListNode* head) {
return head ? mergeSort(head) : nullptr;
}

ListNode* mergeSort(ListNode* head) {
if (!head->next) {
return head;
}
ListNode *p = head, *q = head, *pre = 0;
while (q && q->next ) {
pre = p;
p = p->next;
q = q->next->next;
}
pre->next = nullptr;
return merge(mergeSort(head), mergeSort(p));
}

ListNode* merge(ListNode* l1, ListNode* l2)
{
ListNode dummyHead(0);
auto p = &dummyHead;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2;
return dummyHead.next;
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×