# 148. Sort List (Medium)

https://leetcode.com/problems/sort-list/

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

```Input: 4->2->1->3
Output: 1->2->3->4
```

Example 2:

```Input: -1->5->3->4->0
Output: -1->0->3->4->5```

## Solutions

``````class Solution {

// Employ merge sort algorithm to solve this problem, be careful for the corn cases,

}

int len = 0;
while (p != null) {
len++;
p = p.next;
}

// Find the middle position to split the list into two sub list
int mid = 0;

// Think it over if the len is odd or even
while (mid < (len / 2 - 1)) {
left = left.next;
right = right.next;
mid++;
}

// You must split it. This situation is totally different from those of using
// array to hold elements.
left.next = null;

right = sortList(right);

//merge

// dummy head, easy for insertion
ListNode dummy = new ListNode(-1);
ListNode pointer = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
pointer.next = left;
left = left.next;
pointer = pointer.next;
} else {
pointer.next = right;
right = right.next;
pointer = pointer.next;
}
}

while (left != null) {
pointer.next = left;
pointer = pointer.next;
left = left.next;
}

while (right != null) {
pointer.next = right;
pointer = pointer.next;
right = right.next;
}

return dummy.next;
}
}
``````