Sort List

Problem Link

148. Sort List – LeetCode

Problem Statement

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

You must do it in O(n log n) time and constant space complexity (i.e., not using extra space for data structures like arrays or recursion stack if avoidable).

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

Constraints

• The number of nodes in the list is in the range [0, 5 * 10⁴]

• -10⁵ <= Node.val <= 10⁵

Intuition

This is a linked list sorting problem where:

• The best time complexity possible is O(n log n)

• You can’t use arrays, so no .sort() or converting to array and back

Hence, the optimal approach is to use Merge Sort, which works well on linked lists:

• No random access needed

• Can be done in-place (or with minimal recursion overhead)

Approach: Merge Sort on Linked List

1. Divide the list into two halves using slow and fast pointers to find the middle.

2. Recursively sort each half.

3. Merge the sorted halves using a helper function.

Java Code

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        // Step 1: Split the list into two halves
        ListNode mid = getMiddle(head);
        ListNode left = head;
        ListNode right = mid.next;
        mid.next = null;

        // Step 2: Recursively sort the two halves
        left = sortList(left);
        right = sortList(right);

        // Step 3: Merge the sorted halves
        return merge(left, right);
    }

    private ListNode getMiddle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (left != null && right != null) {
            if (left.val <= right.val) {
                current.next = left;
                left = left.next;
            } else {
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }

        current.next = (left != null) ? left : right;

        return dummy.next;
    }
}

Time and Space Complexity

Dry Run

Input: 4 → 2 → 1 → 3

1. Split into 4 → 2 and 1 → 3

2. Sort both → 2 → 4 and 1 → 3

3. Merge → 1 → 2 → 3 → 4

Conclusion

This problem is a textbook application of merge sort on linked lists, and is commonly asked in interviews to test understanding of:

• Recursion

• Merge logic

• Pointer manipulation in linked lists