# 148 Sort List

### Problem:

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

### Solutions:

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
return null;
}
int length = 0;
while (node != null){
length ++;
node = node.next;
}

ListNode result = mergeSort(globalHead, 0, length -1);
return result;
}
private ListNode mergeSort(ListNode globalHead, int start, int end){
if (start > end){
return null;
}
else if (start == end){
tmp.next = null;
return tmp;
}
else{
//start > end
int mid = (start + end ) /2;
ListNode left = mergeSort(globalHead, start, mid);
ListNode right = mergeSort(globalHead, mid + 1, end);
return merge(left, right);
}
}
private ListNode merge(ListNode left, ListNode right){
while (left!=null && right !=null){
if (left.val < right.val){
now.next = left;
now = now.next;
left = left.next;
}
else{
now.next = right;
now = now.next;
right = right.next;
}//else
}//while
if (left !=null){
now.next = left;
}
if (right !=null){
now.next = right;
}