题目
Sort a linked list in O(n log n) time using constant space complexity.
答案
class Solution {
public ListNode sortList(ListNode head) {
return mergeSort(head, listLen(head));
}
private ListNode split(ListNode head, int splitSize) {
ListNode curr = head;
for(int i = 0; i < splitSize - 1; i++) {
curr = curr.next;
}
ListNode ret = curr.next;
curr.next = null;
return ret;
}
private ListNode merge(ListNode head1, ListNode head2) {
ListNode runner = new ListNode(0), start = runner, list1 = head1, list2 = head2;
while(list1 != null || list2 != null) {
ListNode next = null;
if(list1 == null) {
next = list2;
}
else if(list2 == null) {
next = list1;
}
else {
if(list1.val < list2.val)
next = list1;
else
next = list2;
}
runner.next = next;
runner = next;
}
return start.next;
}
private ListNode mergeSort(ListNode head, int len) {
// Split head into two halves
int splitSize = len / 2;
ListNode list2 = split(head, splitSize);
ListNode sort1 = mergeSort(head, splitSize);
ListNode sort2 = mergeSort(list2, len - splitSize);
ListNode merged = merge(sort1, sort2);
}
private int listLen(ListNode head) {
ListNode curr = head;
int cnt = 0;
while(curr != null) { cnt++; curr = curr.next;}
return cnt;
}
}
