148. Sort List

The Sort List problem is a common interview question that tests how well you understand the strengths and limitations of linked lists. Many candidates instinctively think about array-based sorting techniques, only to run into inefficiencies due to the lack of random access. This problem pushes you to think differently and choose an algorithm that works naturally with linked lists. It is especially useful for learning why merge sort is often the preferred choice in this setting.

Problem statement

You’re given the head of a singly linked list. Your task is to sort the linked list in ascending order and return the head of the sorted list.

Constraints:

• The number of nodes in the list is in the range [0, 5 * 10⁴].
• -10⁵ <= Node.val <= 10⁵

Examples

Why enumerating all possible orders doesn’t scale

One naive approach is to repeatedly scan the list to find the minimum element and rebuild the list one node at a time. This results in O(n^2) time complexity, which is not feasible when the list contains tens of thousands of nodes.

Optimized approach using bottom-up Merge Sort

Merge sort is a natural fit for linked lists because it relies on sequential access and pointer manipulation. A bottom-up merge sort performs the same logical steps as recursive merge sort but avoids recursion entirely.

Instead of dividing the list recursively, we iteratively merge sorted sublists of increasing size:

• First, merge sublists of size 1
• Then size 2
• Then size 3, and so on

This continues until the entire list is merged into a single sorted list.

Why bottom-up Merge Sort works well for Linked Lists

Linked lists allow efficient splitting and merging by reassigning pointers. Bottom-up merge sort takes advantage of this while also eliminating recursion, which saves stack space.

This makes the approach:

• Time-optimal (O(n log n))
• Space-efficient (O(1) extra space
• Safe for very large lists

Step-by-step algorithm

The following algorithmic steps outline how to efficiently sort a linked list in ascending order.

1. If the list is empty or has only one node, return it.
2. Compute the length n of the linked list.
3. Create a dummy node that points to the head to simplify pointer handling.
4. Set step = 1 to represent the current sublist size.
5. While step < n:
   1. Initialize prev to the dummy node and curr to the start of the list.
   2. While curr is not None:
      1. Assign left = curr.
      2. Split the list after step nodes to get right.
      3. Split again after step nodes to get the next starting point.
      4. Merge left and right.
      5. Connect the merged list to prev.next.
      6. Move prev to the end of the merged list.
   3. Double the sublist size: step *= 2.
6. Return dummy.next as the new head.

To better understand the algorithm, let’s walk through an illustration example below:

1 / 5

Python implementation

Let’s look at the code for the solution we just discussed.

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

def sortList(head):
    if head is None or head.next is None:
        return head

    # Step 1: Compute the length of the list
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    dummy = ListNode(0)
    dummy.next = head
    step = 1

    # Step 2: Bottom-up merge sort
    while step < length:
        prev = dummy
        curr = dummy.next

        while curr:
            left = curr
            right = split(left, step)
            curr = split(right, step)

            mergedHead, mergedTail = merge(left, right)
            prev.next = mergedHead
            prev = mergedTail

        step *= 2

    return dummy.next

def split(head, size):
    """
    Split the list after 'size' nodes and return the head of the remaining list.
    """
    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(l1, l2):
    """
    Merge two sorted lists and return both the head and tail of the merged list.
    """
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2

    # Move tail to the end
    while tail.next:
        tail = tail.next

    return dummy.next, tail

def build_linked_list(values):
    """Build a linked list from a Python list."""
    dummy = ListNode(0)
    curr = dummy
    for val in values:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next


def linked_list_to_list(head):
    """Convert a linked list back into a Python list."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


def main():
    test_cases = [
        [4, 2, 1, 3],
        [-1, 5, 3, 4, 0],
        [],
        [1],
        [3, 3, 2, 1]
    ]


    for idx, values in enumerate(test_cases, start=1):
        head = build_linked_list(values)
        sorted_head = sortList(head)
        output = linked_list_to_list(sorted_head)

        print(f"{idx}.\tInput list: {values}")
        print(f"\tSorted list: {output}")
        print("-" * 75)


if __name__ == "__main__":
    main()    

Time complexity

The time complexity of this solution is O(n log n), where n is the number of nodes in the linked list. The list is processed in log n passes, and each pass merges all nodes once, resulting in overall logarithmic-linear performance.

Space complexity

The space complexity of this solution is O(1) extra space. The algorithm sorts the list in-place using pointer manipulation and avoids recursion, so no additional stack space is required.

Edge cases

• Empty list
  • Example: head = [] → output is [].
• Single-node list
  • Example: head = [5] → already sorted.
• List with negative values
  • Example: head = [-3, -1, -2] → correctly sorted to [-3, -2, -1].

Common pitfalls

• Incorrect list splitting: Forgetting to break the list properly can cause infinite loops.
• Losing track of merged tails: Not returning the tail after merging leads to incorrect list connections.
• Using recursive merge sort unintentionally: This defeats the purpose of saving stack space.