LeetCode 148: Sort List

Problem Restatement

We are given the head of a singly linked list.

Return the list after sorting it in ascending order.

The problem asks for an O(n log n) time solution. The follow-up asks whether we can sort the list with constant extra space. The number of nodes is in the range [0, 5 * 10^4], and node values are between -10^5 and 10^5.

Examples

Example 1:

head = [4, 2, 1, 3]

Output:

[1, 2, 3, 4]

Example 2:

head = [-1, 5, 3, 4, 0]

Output:

[-1, 0, 3, 4, 5]

Example 3:

head = []

Output:

[]

Input and Output

Item	Meaning
Input	`head: Optional[ListNode]`
Output	Head of the sorted linked list
Sort order	Ascending
Target time	`O(n log n)`
Follow-up space	`O(1)` extra space

Function shape:

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ...

First Thought: Convert to Array

A simple solution is:

Walk through the linked list.
Store all node values in an array.
Sort the array.
Write the sorted values back to the list.

This is easy, but it uses O(n) extra space and modifies node values instead of rearranging nodes.

The linked-list-native solution is merge sort.

Key Insight

Merge sort fits linked lists well.

For arrays, merge sort needs extra space to merge values.

For linked lists, merging can be done by changing next pointers.

The idea:

Split the list into two halves.
Sort each half recursively.
Merge the two sorted halves.

This gives O(n log n) time because each level processes all nodes once, and there are O(log n) levels.

Finding the Middle

Use slow and fast pointers.

slow = head
fast = head.next

Move:

slow = slow.next
fast = fast.next.next

When fast reaches the end, slow points to the node before the start of the second half.

For:

4 -> 2 -> 1 -> 3

the split becomes:

4 -> 2
1 -> 3

Then we disconnect the halves:

second = slow.next
slow.next = None

Merging Two Sorted Lists

After recursively sorting both halves, we merge them.

Example:

left:  2 -> 4
right: 1 -> 3

Compare the heads:

1 is smaller than 2

Take 1.

Then compare:

2 and 3

Take 2.

Continue until one list is empty.

Result:

1 -> 2 -> 3 -> 4

Algorithm

Use recursive merge sort.

For sortList(head):

If head is None or head.next is None, return head.
Use slow and fast pointers to find the middle.
Split the list into two halves.
Recursively sort the left half.
Recursively sort the right half.
Merge the two sorted halves.
Return the merged head.

Correctness

The base case is correct because an empty list or a one-node list is already sorted.

For a longer list, the algorithm splits it into two smaller linked lists. By the recursive assumption, each half is returned in sorted order.

The merge step repeatedly chooses the smaller head node from the two sorted halves. This keeps the output sorted at every step. Since every node from both halves is appended exactly once, the merged list contains exactly all nodes from the original list.

Therefore, each recursive call returns a sorted version of its input list. Applying this to the original head returns the whole linked list sorted in ascending order.

Complexity

Let n be the number of nodes.

Metric	Value	Why
Time	`O(n log n)`	Each level merges all nodes, and there are `log n` levels
Space	`O(log n)`	Recursive call stack

The merge itself uses O(1) extra pointer space.

Strictly speaking, the recursive version uses O(log n) stack space. A bottom-up iterative merge sort can achieve O(1) extra space.

Implementation

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(second)

        return self.merge(left, right)

    def merge(
        self,
        left: Optional[ListNode],
        right: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy

        while left and right:
            if left.val <= right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next

            tail = tail.next

        if left:
            tail.next = left
        else:
            tail.next = right

        return dummy.next

Code Explanation

The base case handles empty and one-node lists:

if head is None or head.next is None:
    return head

Then we find the middle:

slow = head
fast = head.next

Starting fast at head.next helps split a two-node list into one node and one node.

The loop moves the pointers:

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

Then split:

second = slow.next
slow.next = None

Now head starts the first half, and second starts the second half.

Recursively sort both halves:

left = self.sortList(head)
right = self.sortList(second)

Then merge:

return self.merge(left, right)

The merge function uses a dummy node:

dummy = ListNode(0)
tail = dummy

At each step, attach the smaller node:

if left.val <= right.val:
    tail.next = left
    left = left.next
else:
    tail.next = right
    right = right.next

When one side is empty, append the rest:

if left:
    tail.next = left
else:
    tail.next = right

Return the real merged head:

return dummy.next

Bottom-Up O(1) Space Version

The recursive version is usually accepted and easy to explain.

For the follow-up, we can remove recursion by using bottom-up merge sort.

The idea:

Compute the length of the list.
Merge sorted blocks of size 1.
Then merge blocks of size 2.
Then size 4, 8, and so on.

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        n = 0
        curr = head

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

        dummy = ListNode(0, head)
        size = 1

        while size < n:
            prev = dummy
            curr = dummy.next

            while curr:
                left = curr
                right = self.split(left, size)
                curr = self.split(right, size)

                prev = self.merge_into(left, right, prev)

            size *= 2

        return dummy.next

    def split(
        self,
        head: Optional[ListNode],
        size: int,
    ) -> Optional[ListNode]:
        if head is None:
            return None

        curr = head

        for _ in range(size - 1):
            if curr.next is None:
                break
            curr = curr.next

        next_head = curr.next
        curr.next = None

        return next_head

    def merge_into(
        self,
        left: Optional[ListNode],
        right: Optional[ListNode],
        prev: ListNode,
    ) -> ListNode:
        curr = prev

        while left and right:
            if left.val <= right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next

            curr = curr.next

        curr.next = left if left else right

        while curr.next:
            curr = curr.next

        return curr

This version has:

Metric	Value
Time	`O(n log n)`
Extra space	`O(1)`

It is longer, but it satisfies the follow-up more strictly.

Testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode(0)
    curr = dummy

    for value in values:
        curr.next = ListNode(value)
        curr = curr.next

    return dummy.next

def to_list(head):
    result = []
    curr = head

    while curr:
        result.append(curr.val)
        curr = curr.next

    return result

def run_tests():
    s = Solution()

    head = build_list([4, 2, 1, 3])
    assert to_list(s.sortList(head)) == [1, 2, 3, 4]

    head = build_list([-1, 5, 3, 4, 0])
    assert to_list(s.sortList(head)) == [-1, 0, 3, 4, 5]

    head = build_list([])
    assert to_list(s.sortList(head)) == []

    head = build_list([1])
    assert to_list(s.sortList(head)) == [1]

    head = build_list([1, 2, 3, 4])
    assert to_list(s.sortList(head)) == [1, 2, 3, 4]

    head = build_list([4, 3, 2, 1])
    assert to_list(s.sortList(head)) == [1, 2, 3, 4]

    head = build_list([2, 2, 1, 1])
    assert to_list(s.sortList(head)) == [1, 1, 2, 2]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[4, 2, 1, 3]`	Standard example
`[-1, 5, 3, 4, 0]`	Mixed negative and positive values
`[]`	Empty list
`[1]`	Single node
Already sorted	Should remain sorted
Reverse sorted	Harder ordering case
Duplicates	Equal values handled correctly