Sort List Problem
Description
LeetCode Problem 148.
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
1
2
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
1
2
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:
1
2
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5
Sample C++ Code
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
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(!head || !(head->next)) return head;
//get the linked list's length
ListNode* cur = head;
int length = 0;
while(cur){
length++;
cur = cur->next;
}
ListNode dummy(0);
dummy.next = head;
ListNode *left, *right, *tail;
for(int step = 1; step < length; step <<= 1){
cur = dummy.next;
tail = &dummy;
while(cur){
left = cur;
right = split(left, step);
cur = split(right,step);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
private:
ListNode* split(ListNode *head, int n){
//if(!head) return NULL;
for(int i = 1; head && i < n; i++) head = head->next;
if(!head) return NULL;
ListNode *second = head->next;
head->next = NULL;
return second;
}
ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
ListNode *cur = head;
while(l1 && l2){
if(l1->val > l2->val){
cur->next = l2;
cur = l2;
l2 = l2->next;
}
else{
cur->next = l1;
cur = l1;
l1 = l1->next;
}
}
cur->next = (l1 ? l1 : l2);
while(cur->next) cur = cur->next;
return cur;
}
};