Sort List

Share

Given the head of a linked list, return the list sorted in ascending order. The solution must run in O(n log n) time and use only O(1) extra space (constant space, ignoring call stack).

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: []

Solution Approach - Top-Down Merge Sort

Merge sort is the ideal algorithm for linked lists as it does not require random access and achieves O(n log n) time. The approach is:

  • Divide: Find the middle of the list using the slow/fast pointer technique and split the list into two halves.
  • Conquer: Recursively sort each half.
  • Combine: Merge the two sorted halves using the standard sorted merge operation.
  • Base case: a list of 0 or 1 nodes is already sorted.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class SortList {

    public ListNode sortList(ListNode head) {
        // Base case: 0 or 1 nodes
        if (head == null || head.next == null) return head;

        // Step 1: Find middle and split
        ListNode mid = getMid(head);
        ListNode right = mid.next;
        mid.next = null; // disconnect left and right halves

        // Step 2: Recursively sort both halves
        ListNode leftSorted = sortList(head);
        ListNode rightSorted = sortList(right);

        // Step 3: Merge the sorted halves
        return merge(leftSorted, rightSorted);
    }

    private ListNode getMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next; // using head.next so slow stops at first middle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}
Complexity Analysis:

Time complexity: O(n log n). The list is divided in half log n times and each merge step takes O(n) total.
Space complexity: O(log n) for the recursion call stack. An iterative bottom-up merge sort achieves true O(1) space.