# 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
Output: [1,2,3,4]
``````

Example 2:

``````1
2
Output: [-1,0,3,4,5]
``````

Example 3:

``````1
2
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:

int length = 0;
while(cur){
length++;
cur = cur->next;
}

ListNode dummy(0);
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:

return second;
}

ListNode* merge(ListNode* l1, ListNode* l2, ListNode* 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;
}
};
``````