# [leetcode] Sort List

### Sort List

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

tag: list, sort

9/22/2015 update

a cleaner solution

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//base condition

mid = sortList(mid);

//merge two sorted list
while(mid != NULL && head != NULL){
tail->next = p;
tail = tail->next;
p = p->next;
}
tail->next = mid == NULL? head: mid;
}
//split the list evenly
ListNode * fast, * slow, * prev;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
prev->next = NULL;
return slow;
}
};```

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
}
else{
ListNode * fast, * slow, * prev;
//split list into two parts
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
prev->next = NULL;
ListNode * rightPart = slow;
ListNode * sortedLeftPart = sortList(leftPart);
ListNode * sortedRightPart = sortList(rightPart);
return merge(sortedLeftPart, sortedRightPart);
}
}
ListNode * merge(ListNode * left, ListNode * right){
ListNode * superHead = new ListNode(0);
while(left && right){
if(left->val < right->val){
p->next = left;
left = left->next;
}
else{
p->next = right;
right = right->next;
}
p = p->next;
}
if(left){
p->next = left;
}
if(right){
p->next = right;
}