Skip to main content

Sort List

Sort List: Given the head of a linked list, return *the list after sorting it in ascending order*.

Example 1:​

image

Input: head = [4,2,1,3]
Output: [1,2,3,4]

image

Example 2:​
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:​
Input: head = []
Output: []
Constraints:​
  • The number of nodes in the list is in the range [0, 5 * 10^4].
  • -10^5 <= Node.val <= 10^5

Try this Problem on your own or check similar problems:

  1. Merge Two Sorted Lists
  2. Sort Colors
  3. Insertion Sort List
Solution:​
class Solution {
  public ListNode sortList(ListNode head) {
      if(head == null || head.next == null) return head;

      ListNode dummy = new ListNode(-1, head);
      ListNode slow = dummy, fast = dummy;

      while(fast != null && fast.next != null){
          fast = fast.next.next;
          slow = slow.next;
      }
      ListNode secondHalfHead = slow.next;
      slow.next = null;

      ListNode firstHalfHead = sortList(head);
      secondHalfHead = sortList(secondHalfHead);
      return mergeTwoLists(firstHalfHead, secondHalfHead);
  }

  private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      if(list1 == null || list2 == null) return list1 == null ? list2 : list1;

      ListNode dummy = new ListNode(-1, null), curr = dummy;

      while(list1 != null && list2 != null){
          if(list1.val < list2.val){
              curr.next = list1;
              list1 = list1.next;
          }
          else{
              curr.next = list2;
              list2 = list2.next;
          }

          curr = curr.next;
      }

      if(list1 != null || list2 != null){
          curr.next = list1 != null ? list1 : list2;
      }

      return dummy.next;
  }
}
Time/Space Complexity:​
  • Time Complexity: O(nlogn)
  • Space Complexity: O(logn)
Explanation:​

We already know how to merge lists together using the approach we implemented in Merge Two Sorted Lists so we can just use it here too as the second part of the mergesort process. To break the linked list into two parts (and keep on halving those halves recursively) we can use the slow and fast pointer approach, where the faster pointer is moving 1 node faster than the slower (double the speed), so when the fast arrives at the last element, the slow one will be at the middle. We can use this information because the slow pointer now has next set to the start of the second half of the linked list, while the first half starts at the original list head. To break those halves into two, and prevent infinite loop we do slow.next = null which breaks the connection between the halves. We recursively call the sortList on both halves and merge the two lists using our mergeTwoLists helper function. Note that space complexity here is O(logn) since we have recursion stack only contributing to it, but it is possible to reduce the space complexity down to constant O(1) if we turn this solution into iterative one. Notice that we're breaking the list down to sublists with only one node, then combining those into sorted sublists with two nodes and so on. We can use that information and start diving by some factor (e.g. first all 1-node size lists, than 2-nodes lists...) each time doubling the factor. We would also need to keep track on the tails of all those sublists and pointers showing to the next sublist we want to operate on. The code is given below:

class Solution {
    ListNode tail = new ListNode();
    ListNode nextSubList = new ListNode();

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        int n = getCount(head);
        ListNode start = head;
        ListNode dummyHead = new ListNode();
        for (int size = 1; size < n; size = size * 2) {
            tail = dummyHead;
            while (start != null) {
                if (start.next == null) {
                    tail.next = start;
                    break;
                }
                ListNode mid = split(start, size);
                merge(start, mid);
                start = nextSubList;
            }
            start = dummyHead.next;
        }
        return dummyHead.next;
    }

    ListNode split(ListNode start, int size) {
        ListNode midPrev = start;
        ListNode end = start.next;
        for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
            if (end.next != null) {
                end = (end.next.next != null) ? end.next.next : end.next;
            }
            if (midPrev.next != null) {
                midPrev = midPrev.next;
            }
        }
        ListNode mid = midPrev.next;
        midPrev.next = null;
        nextSubList = end.next;
        end.next = null;
        return mid;
    }

    void merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode newTail = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                newTail.next = list1;
                list1 = list1.next;
                newTail = newTail.next;
            } else {
                newTail.next = list2;
                list2 = list2.next;
                newTail = newTail.next;
            }
        }
        newTail.next = (list1 != null) ? list1 : list2;
        while (newTail.next != null) {
            newTail = newTail.next;
        }
        tail.next = dummyHead.next;
        tail = newTail;
    }

    int getCount(ListNode head) {
        int cnt = 0;
        ListNode ptr = head;
        while (ptr != null) {
            ptr = ptr.next;
            cnt++;
        }
        return cnt;
    }
}