148. Sort List

Problem¶

Sort a singly linked list in ascending order using \(O(n \log n)\) time and \(O(1)\) auxiliary space.

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

Key trick¶

Use bottom-up merge sort: repeatedly merge adjacent runs of sizes \(1, 2, 4, \ldots\) while rewiring existing nodes.

Trap¶

Array sorting uses \(O(n)\) extra space and may leave the linked list cyclic if the final node is not disconnected.
Recursive merge sort uses \(O(\log n)\) call-stack space.
In-place insertion sort is \(O(n^2)\) and requires saving the original next node before rewiring.

Why is it interesting?¶

It combines linked-list pointer manipulation with an iterative merge sort that achieves \(O(n \log n)\) time and \(O(1)\) auxiliary space.

Python solution¶

class Solution:
    def sortList(
        self,
        head: ListNode | None,
    ) -> ListNode | None:
        # The length determines how many run sizes must be merged.
        n = 0
        cur = head

        while cur:
            n += 1
            cur = cur.next

        # The dummy node makes replacement of the head straightforward.
        dummy = ListNode(next=head)

        # One-node runs are initially sorted.
        width = 1

        while width < n:
            # Rebuild the list from merged runs during this pass.
            prev = dummy
            cur = dummy.next

            while cur:
                # Cut out two adjacent runs of at most `width` nodes.
                l = cur
                r = self._split_run(l, width)
                cur = self._split_run(r, width)

                # Merge the detached runs, then attach them to the result.
                merged_head, merged_tail = self._merge_runs(l, r)
                prev.next = merged_head
                prev = merged_tail

            # Each pass doubles the size of sorted runs.
            width *= 2

        return dummy.next

    def _split_run(
        self,
        head: ListNode | None,
        size: int,
    ) -> ListNode | None:
        """Cut after at most `size` nodes and return the following run."""

        if head is None:
            return None

        # Stop at the final node belonging to this run.
        for _ in range(size - 1):
            if head.next is None:
                break

            head = head.next

        # Detach this run from the rest of the list.
        nxt = head.next
        head.next = None

        return nxt

    def _merge_runs(
        self,
        l: ListNode | None,
        r: ListNode | None,
    ) -> tuple[ListNode | None, ListNode]:
        # Return both ends because the caller must append another merged run.
        dummy = ListNode()
        tail = dummy

        while l and r:
            # Take from the left on equality to preserve stability.
            if l.val <= r.val:
                tail.next = l
                l = l.next
            else:
                tail.next = r
                r = r.next

            tail = tail.next

        # Attach the unconsumed run without copying its nodes.
        tail.next = l if l else r

        # Find the actual tail required by the outer merge loop.
        while tail.next:
            tail = tail.next

        return dummy.next, tail

Time: \(O(n \log n)\)
Auxiliary space: \(O(1)\)

Comment on my solution¶

First solution¶

Returning an empty list for empty input is incorrect; the result should be None.
It is insertion sort, so its worst-case time is \(O(n^2)\).
After inserting node, the original next node is lost in the general case because node = node.next follows the newly assigned sorted link.
Save the original next node before every insertion.

Second solution¶

Sorting the node array takes \(O(n)\) auxiliary space, so it does not meet the follow-up requirement.
The memory error is likely caused by a cycle: after relinking the sorted nodes, the final node still retains its old next pointer.
Setting the final node's next to None fixes the cycle, but the solution still uses \(O(n)\) extra space.
Empty input should return None, not an empty list.

Solutions¶

# WRONG
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # O(n^2): bubble sort, insertion sort, selection sort
        # O(nlogn): quick sort, merge sort, heap sort

        if not head:
            return []

        head_sorted = head
        node = head.next

        while node:
            if node.val <= head_sorted.val:
                nxt = node.next
                node.next = head_sorted
                head_sorted = node
                node = nxt
                continue

            prev = head_sorted
            cur = head_sorted.next
            while cur and node.val > cur.val:
                prev = cur
                cur = cur.next
            prev.next = node
            node.next = cur
            node = node.next
        return head_sorted

# WRONG ()
# Updated after reading AI comments
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # O(n^2): bubble sort, insertion sort, selection sort
        # O(nlogn): quick sort, merge sort, heap sort

        if not head:
            return []

        head_sorted = head
        node = head.next

        while node:
            if node.val <= head_sorted.val:
                nxt = node.next
                node.next = head_sorted
                head_sorted = node
                node = nxt
                continue

            prev = head_sorted
            cur = head_sorted.next
            while cur and node.val > cur.val:
                prev = cur
                cur = cur.next

            nxt = node.next

            prev.next = node
            node.next = cur
            node = nxt
        return head_sorted


# WORKS (but don't pass test on LeetCode)
# Memory Limit Exceeded: 0/30 testcases passed
# input: [4,2,1,3]
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # O(nlogn) with O(n) space
        if not head:
            return []

        nodes = []
        i = 0 # for breaking tie
        while head:
            nodes.append((head.val, i, head))
            head = head.next
            i += 1
        nodes.sort()
        dummy = ListNode()
        tail = dummy
        for _, _, node in nodes:
            tail.next = node
            tail = tail.next

        return dummy.next

# WORKS (and pass leetcode tests)
# Updated after reading AI solution
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # O(nlogn) with O(n) space
        if not head:
            return None

        nodes = []
        i = 0 # for breaking tie
        while head:
            nodes.append((head.val, i, head))
            head = head.next
            i += 1
        nodes.sort()
        dummy = ListNode()
        tail = dummy
        for _, _, node in nodes:
            tail.next = node
            tail = tail.next

        # To avoid cycle, set the final node's next to None
        nodes[-1][2].next = None

        return dummy.next