Algorithm Overview

1. Split: Use slow-fast pointer technique to locate the midpoint and partition the list into two halves.
2. Recurse: Apply the same sorting procedure recursively on both halves.
3. Merge: Combine the two sorted sublists into a single sorted list using a linear-time merge step.

Implementation

class ListNode {
    int value;
    ListNode next;
    
    ListNode(int val) { this.value = val; }
    ListNode(int val, ListNode nxt) { this.value = val; this.next = nxt; }
}

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

        // Step 1: Split at midpoint
        ListNode tailOfFirstHalf = findMidpointPredecessor(head);
        ListNode secondHalfHead = tailOfFirstHalf.next;
        tailOfFirstHalf.next = null;

        // Step 2: Recursively sort both halves
        ListNode sortedLeft = sortLinkedList(head);
        ListNode sortedRight = sortLinkedList(secondHalfHead);

        // Step 3: Merge sorted halves
        return mergeSortedLists(sortedLeft, sortedRight);
    }

    private ListNode findMidpointPredecessor(ListNode start) {
        ListNode slow = start;
        ListNode fast = start.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode mergeSortedLists(ListNode a, ListNode b) {
        ListNode sentinel = new ListNode(0);
        ListNode current = sentinel;

        while (a != null && b != null) {
            if (a.value <= b.value) {
                current.next = a;
                a = a.next;
            } else {
                current.next = b;
                b = b.next;
            }
            current = current.next;
        }

        current.next = (a != null) ? a : b;
        return sentinel.next;
    }
}

Why Merge Sort Over Alternatives?

• Random access limitation: Unlike arrays, linked lists lack O(1) index-based access—making quicksort pivot selection and heap-based operations inefficient or impractical.
• Time complexity: Bubble or selection sorts yield O(n²), which becomes infeasible for large inputs. Merge sort guarantees O(n log n) with predictable performance.
• Stability and simplicity: The divide-and-conquer structure maps cleanly onto pointer manipulation; no swapping or complex in-place rearrangements are needed.

Why Does Fast Start One Node Ahead?

Initializing fast = start.next ensures that when the list has an even number of nodes, slow lands exactly at the last node of the first half. This enables clean disconnection (tailOfFirstHalf.next = null) without off-by-one errors or special-case handling for length parity.