148. Sort List

Reference: LeetCode
Difficulty: MediumSlow/Fast Pointers

My Post: Java Mergesort for Sort List (Recursion & Iteration)

Problem

Sort a linked list in $O(N\log{N})$ time using constant space complexity.

Example:

Input: 4->2->1->3
Output: 1->2->3->4

Input: 4->2->1->3->5
Output: 1->2->3->4->5

Analysis

Naive (Extra Space)

Note: Be careful of linked list generation.

public ListNode naiveSort(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  // toArray
  List<ListNode> array = new ArrayList<>();
  ListNode p = head;
  while (p != null) {
    array.add(p);
    p = p.next;
  }
  // sort
  Comparator<ListNode> comp = (ListNode o1, ListNode o2) -> (o1.val - o2.val);
  array.sort(comp);
  // generate linked list
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;
  for (int i = 0; i < array.size(); ++i) {
    prev.next = array.get(i);
    prev = prev.next;
  }
  prev.next = null;
  return dummy.next;
}

Time: $O(N + N\log{N} + N) = O(N\log{N})$
Space: $O(N)$

Mergesort + Slow/Fast Pointers

Recursion

Note:

• It seems bad to use right-leaning splitInHalf, because you can’t split the list (set the previous node of mid to null).
• Since we need to set mid.next to null, we can do right mergeSort first. Clean code.

public ListNode sortList(ListNode head) {
  return mergesort(head);
}

private ListNode mergesort(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  ListNode[] splitResult = splitInHalf(head); // O(N)
  ListNode left = mergesort(splitResult[0]);
  ListNode right = mergesort(splitResult[1]);
  return mergeList(left, right); // O(N)
}
  
private ListNode mergeList(ListNode head1, ListNode head2) {
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;
  
  while (head1 != null && head2 != null) {
    if (head1.val < head2.val) {
      prev.next = head1;
      head1 = head1.next;
    } else {
      prev.next = head2;
      head2 = head2.next;
    }
    prev = prev.next;
  }
  
  if (head1 != null) prev.next = head1;
  if (head2 != null) prev.next = head2;
  
  return dummy.next;
}


private ListNode[] splitInHalf(ListNode head) {
  if (head == null) {
    return new ListNode[] { null, null };
  }
  // left-leaning
  ListNode slow = head;
  ListNode fast = head;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  ListNode[] result = new ListNode[] { head, slow.next };
  slow.next = null;
  return result;
}

Time: $O(N\log{N})$
Space: $O(\log{N})$

Iteration

Each time we double n.

• split(head, n) that splits input head into [n nodes, the rest].
  • We need to handle a case that n is larger than the number of available nodes.
• mergeList(n1, n2) returns [head, tail] of the merged list.

Note: In each loop, p should be initialized with dummy.next rather than head, since head might be changing.

public ListNode sortList(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  int len = getLength(head);
  ListNode dummy = new ListNode(-1);
  dummy.next = head;

  for (int n = 1; n < len; n *= 2) { // splitting unit
    ListNode p = dummy.next; // head may be changed!!!
    ListNode prev = dummy;
    while (p != null) {
      // split
      ListNode[] result = split(p, n);
      ListNode left = result[0];
      ListNode rest = result[1];
      result = split(rest, n);
      ListNode right = result[0];
      rest = result[1]; // might be null
      // merge
      result = mergeList(left, right);
      prev.next = result[0];
      // update
      prev = result[1];
      p = rest;
    }
  }
  return dummy.next;
}

Helper functions:

// Splits into [n nodes, rest part]
private ListNode[] split(ListNode head, int n) {
  if (head == null || head.next == null) {
    return new ListNode[] { head, null };
  }
  ListNode p = head;
  while (n > 1 && p.next != null) {
    p = p.next;
    --n;
  } // p stops at the n-th node (so it should be n > 1)
  ListNode rest = p.next;
  p.next = null;
  return new ListNode[] { head, rest };
}

// Returns [first node, last node] after merging
private ListNode[] mergeList(ListNode n1, ListNode n2) { // n1, n2 are sorted
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;
  while (n1 != null && n2 != null) {
    if (n1.val < n2.val) {
      prev.next = n1;
      n1 = n1.next;
    } else {
      prev.next = n2;
      n2 = n2.next;
    }
    prev = prev.next;
  }
  prev.next = (n1 != null) ? n1 : n2;

  // reach the tail
  while (prev.next != null) prev = prev.next;
  return new ListNode[] { dummy.next, prev };
}

// Get Length
private int getLength(ListNode x) { ... }

Tips for Slow/Fast Pointers

Note: Use two pointers to find the middle node in the list. But there are two cases: left-leaning and right-leaning.

The difference lies in the while condition.

• Left-leaning: while (fast.next != null && fast.next.next != null) You can see this as a stricter constraint
• Right-leaning: while (fast != null && fast.next != null)

// Left-leaning
// 1  2  3  4  5
// s  s  s
// f     f     f
// ----------
// 1  2  3  4
// s  s
// f     f
private ListNode findMid(ListNode x) {
  if (x == null || x.next == null) {
    return x;
  }
  ListNode slow = x; // left-leaning
  ListNode fast = x;
  while (fast.next != null && fast.next.next != null) { // here is the different
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

```java
// Right-leaning
// ----------
// 1  2  3  4  5
// s  s  s
// f     f     f
// ----------
// 1  2  3  4
// s  s  s
// f     f     f
private ListNode findMid(ListNode x) {
  if (x == null || x.next == null) {
    return x;
  }
  ListNode slow = x; // right-leaning
  ListNode fast = x;
  
  while (fast != null && fast.next != null) { // here is the different
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}