Sort List [Linked List MergeSort]

148.Sort List

Linked List

Sorting

Divide and Conquer

Two Pointers

Problem Statement:

Given the head of a linked list, return the list after sorting it in ascending order. Must use O(n log n) time complexity and O(1) extra space.

Example:

Input:

head = [4,2,1,3]

→

Output:

[1,2,3,4]

Algorithm:

1. Use merge sort approach with linked list
2. Find middle using slow/fast pointers
3. Recursively sort both halves
4. Merge sorted halves

Complexity:

Time: O(n log n) | Space: O(log n) for recursion stack

Java Solution:

public ListNode sortList(ListNode head) {
    // Base case: empty list or single node
    if (head == null || head.next == null)
        return head;
    
    // Step 1: Find middle using slow/fast pointers
    ListNode prev = null, slow = head, fast = head;
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null;  // Cut the list in half
    
    // Step 2: Recursively sort both halves
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    // Step 3: Merge sorted halves
    return merge(l1, l2);
}

private ListNode merge(ListNode l1, ListNode l2) {
    // Create dummy node for easier merging
    ListNode dummy = new ListNode(0), p = dummy;
    
    // Merge while both lists have nodes
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
    
    // Attach remaining nodes
    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    
    return dummy.next;
}

Python Solution:

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # Base case: empty list or single node
    if not head or not head.next:
        return head
    
    # Step 1: Find middle using slow/fast pointers
    prev = slow = fast = head
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    prev.next = None  # Cut the list in half
    
    # Step 2: Recursively sort both halves
    l1 = self.sortList(head)
    l2 = self.sortList(slow)
    
    # Step 3: Merge sorted halves
    return self.merge(l1, l2)
    
def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
    # Create dummy node for easier merging
    dummy = p = ListNode(0)
    
    # Merge while both lists have nodes
    while l1 and l2:
        if l1.val < l2.val:
            p.next = l1
            l1 = l1.next
        else:
            p.next = l2
            l2 = l2.next
        p = p.next
    
    # Attach remaining nodes
    p.next = l1 or l2
    return dummy.next

C++ Solution:

ListNode* sortList(ListNode* head) {
    // Base case: empty list or single node
    if (!head || !head->next)
        return head;
    
    // Step 1: Find middle using slow/fast pointers
    ListNode *prev = nullptr, *slow = head, *fast = head;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = nullptr;  // Cut the list in half
    
    // Step 2: Recursively sort both halves
    ListNode* l1 = sortList(head);
    ListNode* l2 = sortList(slow);
    
    // Step 3: Merge sorted halves
    return merge(l1, l2);
}

ListNode* merge(ListNode* l1, ListNode* l2) {
    // Create dummy node for easier merging
    ListNode dummy(0);
    ListNode* p = &dummy;
    
    // Merge while both lists have nodes
    while (l1 && l2) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
        } else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    
    // Attach remaining nodes
    if (l1) p->next = l1;
    if (l2) p->next = l2;
    
    return dummy.next;
}

Hello, World!