Total Accepted: 90190
Total Submissions: 331787
Difficulty: Medium
Contributors: Admin
Sort a linked list in O(n log n) time using constant space complexity.
Hide Tags
Linked List Sort
Hide Similar Problems
(E) Merge Two Sorted Lists (M) Sort Colors (M) Insertion Sort List
// 12/23/2016 lake tahoe
public class SortList {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
// step 1. cut the list to two halves
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
// step 2. sort each half
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
// step 3. merge l1 and l2
return merge(l1, l2);
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode l = new ListNode(0), p = l;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null)
p.next = l1;
if (l2 != null)
p.next = l2;
return l.next;
}
}
