Sorting a Linked List Using Divide-and-Conquer

To sort a singly linked list efficiently, we can apply the merge sort algorithm which ensures O(n log n) time complexity. There are two primary approaches: top-down (recursive) and bottom-up (iterative). Below is an implementation of the recursive variant.

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

        // Find the midpoint using fast/slow pointers
        ListNode midPrev = findMidPrev(head);
        ListNode secondHalf = midPrev.next;
        midPrev.next = null;

        // Recursively sort both halves
        ListNode leftSorted = sortList(head);
        ListNode rightSorted = sortList(secondHalf);

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

    private ListNode findMidPrev(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        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 current = dummy;

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

        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

How It Works:

1. Divide: Split the list into two halves by finding the node just before the middle using the fast/slow pointer technique.
2. Conquer: Recursively sort each half.
3. Merge: Combine the two sorted halves into one sorted list.

Example Walkthrough:

Given input list: 4 -> 2 -> 1 -> 3

• The midpoint calculation splits it into [4, 2] and [1, 3].
• Each sublist is further divided until single-node lists remain.
• They are then merged back in sorted order: 1 -> 2 -> 3 -> 4.

Handling Odd-Length Lists:

If the number of nodes is odd, the first half will have one fewer element than the second. For example:

• List: 1 -> 2 -> 3 -> 4 -> 5
• Splits into: [1, 2, 3] and [4, 5]

Bottom-Up Merge Sort (Iterative Approach)

An alternative approach avoids recursion entirely by iteratively merging sublists of increasing size.

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

        int length = getLength(head);
        ListNode dummy = new ListNode(0, head);

        for (int size = 1; size < length; size *= 2) {
            ListNode prev = dummy;
            ListNode curr = dummy.next;

            while (curr != null) {
                ListNode part1 = curr;
                ListNode part2 = split(part1, size);
                curr = split(part2, size);

                ListNode merged = merge(part1, part2);
                prev.next = merged;

                while (prev.next != null)
                    prev = prev.next;

                prev.next = curr;
            }
        }

        return dummy.next;
    }

    private int getLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    private ListNode split(ListNode start, int step) {
        if (start == null) return null;
        for (int i = 1; i < step && start.next != null; i++) {
            start = start.next;
        }
        ListNode nextPart = start.next;
        start.next = null;
        return nextPart;
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

Key Concepts:

• Size Doubling: Starts with sublists of size 1, merges pairs, then doubles the size for the next iteration.
• In-place Merging: Uses helper functions to split and merge segments without additional data structures.

Summary:

Both implementations utilize divide-and-conquer principles to achieve efficient sorting of linked lists. While the recursive version is more intuitive, the iterative method avoids potential stack overflow issues with very long lists.