Sort List

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

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.   public ListNode sortList(ListNode head) {
  11.     if (head == null || head.next == null)
  12.       return head;
  14.     // step 1. cut the list to two halves
  15.     ListNode prev = null, slow = head, fast = head;
  17.     while (fast != null && fast.next != null) {
  18.       prev = slow;
  19.       slow = slow.next;
  20.       fast = fast.next.next;
  21.     }
  23.     prev.next = null;
  25.     // step 2. sort each half
  26.     ListNode l1 = sortList(head);
  27.     ListNode l2 = sortList(slow);
  29.     // step 3. merge l1 and l2
  30.     return merge(l1, l2);
  31.   }
  33.   ListNode merge(ListNode l1, ListNode l2) {
  34.     ListNode l = new ListNode(0), p = l;
  36.     while (l1 != null && l2 != null) {
  37.       if (l1.val < l2.val) {
  38.         p.next = l1;
  39.         l1 = l1.next;
  40.       } else {
  41.         p.next = l2;
  42.         l2 = l2.next;
  43.       }
  44.       p = p.next;
  45.     }
  47.     if (l1 != null)
  48.       p.next = l1;
  50.     if (l2 != null)
  51.       p.next = l2;
  53.     return l.next;
  54.   }
  55. }