Sort List - A Merge Sort Approach for Linked Lists (Java)

Hello everyone! Today, we're tackling "Sort List" (LeetCode #148), a problem that asks us to sort a given linked list.

While we could convert the linked list to an array, sort it, and then convert it back, the most efficient approach, especially for linked lists, is Merge Sort. Merge sort leverages the linked list's structure well and avoids the O(N) space overhead of algorithms like quicksort in the worst case.

---

Understanding the Problem:

You are given the head of a singly linked list. Your task is to sort this list in ascending order and return the head of the sorted list.

Examples:

• Example 1:

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

  • Output: [1, 2, 3, 4]

• Example 2:

  • Input: head = [-1, 5, 3, 4, 0]

  • Output: [-1, 0, 3, 4, 5]

• Example 3:

  • Input: head = []

  • Output: [] (Handle the empty list case!)

---

My Thought Process & Approach (Merge Sort for Linked Lists):

Merge sort is a divide-and-conquer algorithm that works as follows:

1. Divide: Recursively split the linked list into two halves until you have sublists of size 0 or 1 (which are inherently sorted).

2. Conquer (Merge): Merge the sorted sublists back together to produce new sorted sublists. Repeat this merging process until you have a single sorted list.

Why is Merge Sort good for Linked Lists?

• Efficient Splitting: Finding the middle of a linked list can be done in O(N) time, but merge sort's recursive nature means this split is done on smaller and smaller sublists.

• Efficient Merging: Merging two sorted linked lists can be done in O(M + N) time (where M and N are the lengths of the sublists) by simply comparing the heads of the lists and linking nodes in the correct order.

• Avoids Random Access: Unlike quicksort (which has O(N log N) average time but O(N^2) worst-case time for linked lists due to the difficulty of random access), merge sort doesn't rely on random access.

Algorithm Steps:

1. Base Case: If the list is empty (head == null) or has only one node (head.next == null), it's already sorted, so return head.

2. Split the List (split function):

   • Use the fast and slow pointer technique to find the middle of the linked list.

     • temp (fast pointer) moves two steps at a time.

     • half (slow pointer) moves one step at a time.

     • When temp reaches the end, half will be at the middle node (or the node just before the middle if the list has an even number of nodes).

   • Break the list into two sublists:

     • A: From the original head to half.

     • temp: From half.next to the end.

   • Set half.next = null to properly terminate the first sublist (A).

   • Return an ArrayList containing the heads of these two sublists (A and temp).

3. Recursive Sort: Recursively call sortList on both sublists (sortedLeft = sortList(res.get(0)) and sortedRight = sortList(res.get(1))). This will continue to split the lists until the base case is reached.

4. Merge the Sorted Sublists (mergeTwoLists function):

   • This function is the same as in the "Merge Two Sorted Linked Lists" problem. It takes two sorted linked lists (A and B) and merges them into a single sorted list.

   • It iteratively compares the heads of the two lists, picking the smaller node and appending it to the merged list.

   • It handles cases where one list becomes empty before the other.

---

Java Code Implementation:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
     if(head==null || head.next==null){
            return head;
        }
        ArrayList<ListNode> res = split(head);
        if(res.isEmpty()){
            return head;
        }
        ListNode sortedLeft = sortList(res.get(0));
        ListNode sortedRight = sortList(res.get(1));
        return mergeTwoLists(sortedLeft, sortedRight);
    }
    public ArrayList<ListNode> split(ListNode A) {
        ArrayList<ListNode> res = new ArrayList<ListNode>();
        if(A==null){
            return res;
        }
        if(A.next==null){
            return res;
        }
        ListNode temp = A;
        ListNode half = A;
        while(temp.next!= null && temp.next.next!=null && half.next!=null){
            temp = temp.next.next;
            half = half.next;
        }
        temp = half.next;
        half.next = null;
        res.add(A);
        res.add(temp);
        return res;
    }
    public ListNode mergeTwoLists(ListNode A, ListNode B) {
        if(A == null && B == null){
            return null;
        }
        if(A==null){
            return B;
        }
        if(B==null){
            return A;
        }
        ListNode prim;
        ListNode sec;
        if(A.val<B.val){
            prim = A;
            sec = B;
        }
        else{
            prim = B;
            sec = A;
        }
        ListNode P = prim;
        while(prim!=null && sec!= null){
            while(prim.next!=null && prim.next.val<=sec.val){
                prim = prim.next;
            }
            ListNode temp = sec;
            temp = temp.next;
            sec.next = prim.next;
            prim.next = sec;
            sec = temp;
            prim = prim.next;
        }
        if(sec!=null){
            prim.next = sec;
        }
        return P;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N log N)

  • Merge sort has a time complexity of O(N log N) in all cases (best, average, and worst).

    • The splitting step (finding the middle) takes O(N) time, but this is done on smaller and smaller sublists due to the recursion.

    • The merging step takes O(M + N) time to merge two lists of size M and N.

  • The recursion depth is log N (due to the repeated halving), and at each level, we perform O(N) work for merging.

• Space Complexity: O(log N) (Auxiliary Space)

  • The dominant space complexity comes from the recursion call stack. The maximum depth of the recursion is log N (due to the halving of the list).

  • Each recursive call adds a frame to the stack, so the space used by the stack is proportional to the recursion depth, making it O(log N).

  • (Note: While the split function uses an ArrayList, it only ever stores two ListNode objects, so it's O(1) extra space. The mergeTwoLists function operates in-place, so it's also O(1) extra space.)