Sort a Linked List (Merge Sort Approach)

Problem Statement

Sort a singly linked list in ascending order and return the new head. Aim for O(n log n) time.

Example

Input:  4 -> 2 -> 1 -> 3
Output: 1 -> 2 -> 3 -> 4

Approach

Merge sort suits linked lists because it needs only sequential access. Find the middle with slow/fast pointers, split the list in two, recursively sort each half, then merge the two sorted lists with a dummy-head merge. No random access or extra array is required.

Complexity

• Time: O(n log n)
• Space: O(log n) recursion stack

Solution Code

Python

def sortList(head):
    if not head or not head.next:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left = sortList(head)
    right = sortList(mid)
    return _merge(left, right)

def _merge(a, b):
    dummy = ListNode(0)
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a; a = a.next
        else:
            tail.next = b; b = b.next
        tail = tail.next
    tail.next = a if a else b
    return dummy.next

Java

ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode mid = slow.next;
    slow.next = null;
    ListNode left = sortList(head), right = sortList(mid);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (left != null && right != null) {
        if (left.val <= right.val) { tail.next = left; left = left.next; }
        else { tail.next = right; right = right.next; }
        tail = tail.next;
    }
    tail.next = (left != null) ? left : right;
    return dummy.next;
}

C++

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* slow = head; ListNode* fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* mid = slow->next; slow->next = nullptr;
    ListNode* left = sortList(head); ListNode* right = sortList(mid);
    ListNode dummy(0); ListNode* tail = &dummy;
    while (left && right) {
        if (left->val <= right->val) { tail->next = left; left = left->next; }
        else { tail->next = right; right = right->next; }
        tail = tail->next;
    }
    tail->next = left ? left : right;
    return dummy.next;
}

Key Takeaways

• Merge sort is the natural fit for linked lists (sequential access only).
• Quick sort is awkward here because lists lack O(1) random access.
• Reference: LeetCode 148 (Sort List).