148 Sort List¶
Problem:¶
Sort a linked list in O(n log n) time using constant space complexity.
Solutions:¶
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null){
return null;
}
int length = 0;
ListNode node = head;
while (node != null){
length ++;
node = node.next;
}
ListNode globalHead = new ListNode(-1);
globalHead.next = head;
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){
ListNode tmp = globalHead.next;
globalHead.next = globalHead.next.next;
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){
ListNode fakeHead = new ListNode(-1);
ListNode now = fakeHead;
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;
}
return fakeHead.next;
}
}