LeetCode 148 - Sort List

The problem asks us to sort a singly linked list in ascending order and return the head of the sorted list. The input is the head node of a linked list. Each node contains an integer value and a pointer to the next node.

leetcodemediumlinked-listtwo-pointersdivide-and-conquersortingmerge-sort

LeetCode Problem 148

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort

Solution

Problem Understanding

The problem asks us to sort a singly linked list in ascending order and return the head of the sorted list.

The input is the head node of a linked list. Each node contains an integer value and a pointer to the next node. Unlike arrays, linked lists do not support direct indexing, so operations like random access are expensive. This detail strongly influences which sorting algorithms are practical.

The output must be another linked list containing the same nodes, but arranged so that the node values appear in non decreasing order.

The constraints are important:

  • The list can contain up to 5 * 10^4 nodes.
  • Node values range from -10^5 to 10^5.

A naive O(n^2) sorting algorithm such as bubble sort or insertion sort may pass small inputs, but it becomes too slow for lists containing tens of thousands of nodes. The follow up requirement explicitly asks for an O(n log n) solution with constant auxiliary memory, which strongly hints toward merge sort.

Several edge cases are important:

  • The list may be empty.
  • The list may contain only one node.
  • The list may already be sorted.
  • The list may be reverse sorted.
  • The list may contain duplicate values.
  • The list may contain negative numbers.

Because the structure is a linked list, careful pointer handling is required to avoid cycles, lost nodes, or broken links.

Approaches

Brute Force Approach

A straightforward solution is to copy all node values into an array, sort the array, then rebuild or overwrite the linked list.

The algorithm works like this:

  1. Traverse the linked list and store all values in an array.
  2. Sort the array using a built in sorting algorithm.
  3. Traverse the linked list again and overwrite node values using the sorted array.

This produces the correct result because sorting the array guarantees the values are placed in ascending order.

However, this approach uses additional memory proportional to the size of the list. The follow up specifically asks for constant extra space, so this approach does not satisfy the optimal requirement.

Another brute force possibility is bubble sort directly on the linked list, but that requires O(n^2) time and becomes too slow for large inputs.

Optimal Approach

The key insight is that merge sort works exceptionally well on linked lists.

Merge sort divides the list into two halves, recursively sorts each half, then merges the sorted halves together.

This approach is ideal for linked lists because:

  • Splitting a linked list can be done efficiently using slow and fast pointers.
  • Merging two sorted linked lists can be done in linear time without extra arrays.
  • Merge sort guarantees O(n log n) time complexity.

Unlike arrays, linked lists do not support efficient random access, so algorithms like quicksort or heapsort are less suitable. Merge sort naturally fits the sequential structure of linked lists.

Approach Time Complexity Space Complexity Notes
Brute Force Array Conversion O(n log n) O(n) Copy values into array, sort, rewrite list
Optimal Merge Sort O(n log n) O(log n) Recursive merge sort using linked list splitting

Algorithm Walkthrough

Optimal Merge Sort Algorithm

  1. Handle the base case.

If the list is empty or contains only one node, it is already sorted. Return the head immediately. 2. Split the linked list into two halves.

Use two pointers:

  • slow moves one step at a time.
  • fast moves two steps at a time.

When fast reaches the end, slow will be near the middle.

Keep track of the node before slow so the list can be disconnected into two separate halves. 3. Recursively sort the left half.

Call sortList on the first half of the list. 4. Recursively sort the right half.

Call sortList on the second half of the list. 5. Merge the two sorted halves.

Use a standard linked list merge procedure:

  • Compare the current nodes from both lists.
  • Attach the smaller node to the result.
  • Move forward in the chosen list.
  • Continue until one list is exhausted.
  • Attach the remaining nodes.
  1. Return the merged sorted list.

The merged list is fully sorted because both halves were already recursively sorted before merging.

Why it works

Merge sort works because of the divide and conquer principle.

At every recursive level:

  • The list is split into smaller sublists.
  • Eventually, each sublist contains one node, which is trivially sorted.
  • The merge step combines two already sorted lists into one larger sorted list.

The merge operation preserves sorted order because it always selects the smallest available element from the two input lists.

Since every level processes all n nodes and there are log n levels of recursion, the total runtime is O(n log n).

Python Solution

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

from typing import Optional

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

        # Split the list into two halves
        slow = head
        fast = head
        prev = None

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

        # Disconnect the left half from the right half
        prev.next = None

        # Recursively sort both halves
        left_sorted = self.sortList(head)
        right_sorted = self.sortList(slow)

        # Merge the sorted halves
        return self.merge(left_sorted, right_sorted)

    def merge(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode]
    ) -> Optional[ListNode]:

        dummy = ListNode(0)
        current = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next

            current = current.next

        if list1:
            current.next = list1
        else:
            current.next = list2

        return dummy.next

The implementation begins with the base case. If the list is empty or has only one node, it is already sorted.

The slow and fast pointer technique identifies the midpoint of the list. The prev pointer tracks the node before slow, allowing the list to be disconnected cleanly into two halves.

After splitting, the function recursively sorts both halves. Because recursion continues until single node lists are reached, every recursive call eventually returns a sorted sublist.

The merge helper function combines two sorted linked lists. A dummy node simplifies pointer handling by providing a stable starting point for the merged result.

The merge logic repeatedly chooses the smaller current node between the two lists. Once one list is exhausted, the remaining nodes from the other list are appended directly.

Finally, the merged sorted list is returned.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    // Split the list into two halves
    slow := head
    fast := head
    var prev *ListNode

    for fast != nil && fast.Next != nil {
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Disconnect the left half
    prev.Next = nil

    // Recursively sort both halves
    leftSorted := sortList(head)
    rightSorted := sortList(slow)

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

func merge(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            current.Next = list1
            list1 = list1.Next
        } else {
            current.Next = list2
            list2 = list2.Next
        }

        current = current.Next
    }

    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }

    return dummy.Next
}

The Go implementation follows the same algorithmic structure as the Python version.

Go uses nil instead of None for empty pointers. The dummy node is created using &ListNode{}. Recursive function calls work naturally because linked lists are pointer based structures.

One important detail is explicitly disconnecting the left half using prev.Next = nil. Without this step, recursion would continue infinitely because both recursive calls would still reference overlapping portions of the list.

Worked Examples

Example 1

Input:

4 -> 2 -> 1 -> 3

Step 1: Split the list

Using slow and fast pointers:

Iteration slow fast
Start 4 4
1 2 1
2 1 null

The list is split into:

Left:  4 -> 2
Right: 1 -> 3

Step 2: Recursively sort left half

Split:

4 -> 2

Into:

4
2

Merge result:

2 -> 4

Step 3: Recursively sort right half

Split:

1 -> 3

Into:

1
3

Merge result:

1 -> 3

Step 4: Merge sorted halves

Merge:

2 -> 4
1 -> 3

Comparison sequence:

Compare Chosen Node Result
2 vs 1 1 1
2 vs 3 2 1 -> 2
4 vs 3 3 1 -> 2 -> 3
Remaining 4 4 1 -> 2 -> 3 -> 4

Final result:

1 -> 2 -> 3 -> 4

Example 2

Input:

-1 -> 5 -> 3 -> 4 -> 0

Splitting process

First split:

Left:  -1 -> 5
Right: 3 -> 4 -> 0

Sort left:

-1 -> 5

Already sorted after merge.

Sort right:

3 -> 4 -> 0

Further splits:

3
4 -> 0

Then:

4
0

Merge:

0 -> 4

Merge with 3:

0 -> 3 -> 4

Final merge:

-1 -> 5
0 -> 3 -> 4

Result:

-1 -> 0 -> 3 -> 4 -> 5

Example 3

Input:

[]

The list is empty, so the base case immediately returns None.

Output:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Each level processes all nodes, and there are log n recursive levels
Space O(log n) Recursive call stack depth from merge sort recursion

The merge operation processes each node exactly once per recursive level. Since the list is repeatedly divided in half, the recursion depth is logarithmic.

Although merge sort on linked lists can theoretically achieve constant auxiliary space using an iterative bottom up approach, this recursive implementation uses O(log n) stack space due to recursion.

Test Cases

# Helper functions for testing

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

def build_list(values):
    dummy = ListNode()
    current = dummy

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

    return dummy.next

def list_to_array(head):
    result = []

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

    return result

solution = Solution()

# Example 1
head = build_list([4, 2, 1, 3])
assert list_to_array(solution.sortList(head)) == [1, 2, 3, 4]  # basic unsorted list

# Example 2
head = build_list([-1, 5, 3, 4, 0])
assert list_to_array(solution.sortList(head)) == [-1, 0, 3, 4, 5]  # includes negative numbers

# Example 3
head = build_list([])
assert list_to_array(solution.sortList(head)) == []  # empty list

# Single node
head = build_list([7])
assert list_to_array(solution.sortList(head)) == [7]  # single element

# Already sorted
head = build_list([1, 2, 3, 4, 5])
assert list_to_array(solution.sortList(head)) == [1, 2, 3, 4, 5]  # already sorted

# Reverse sorted
head = build_list([5, 4, 3, 2, 1])
assert list_to_array(solution.sortList(head)) == [1, 2, 3, 4, 5]  # worst ordering

# Duplicate values
head = build_list([4, 2, 2, 1, 4])
assert list_to_array(solution.sortList(head)) == [1, 2, 2, 4, 4]  # duplicates

# All equal values
head = build_list([3, 3, 3, 3])
assert list_to_array(solution.sortList(head)) == [3, 3, 3, 3]  # identical elements

# Negative values only
head = build_list([-5, -10, -3, -1])
assert list_to_array(solution.sortList(head)) == [-10, -5, -3, -1]  # all negatives

# Large gap values
head = build_list([100000, -100000, 0])
assert list_to_array(solution.sortList(head)) == [-100000, 0, 100000]  # constraint extremes
Test Why
[4,2,1,3] Validates standard unsorted input
[-1,5,3,4,0] Tests negative and positive values together
[] Verifies empty list handling
[7] Verifies single node base case
[1,2,3,4,5] Ensures already sorted lists remain correct
[5,4,3,2,1] Tests reverse sorted worst ordering
[4,2,2,1,4] Validates duplicate handling
[3,3,3,3] Tests identical values
[-5,-10,-3,-1] Ensures negative sorting correctness
[100000,-100000,0] Tests extreme constraint values

Edge Cases

Empty List

An empty linked list is represented by head = None. This case can easily cause null pointer errors if not handled early. The implementation checks for an empty list at the beginning of the function and immediately returns head.

Single Node List

A list containing only one node is already sorted. Without the base case, recursion would continue unnecessarily and could lead to incorrect splitting behavior. The condition if not head or not head.next correctly stops recursion for single node lists.

Duplicate Values

Lists with duplicate values can expose issues in merge logic, especially if comparisons are not handled carefully. The implementation uses <= during merging, which preserves correct ordering and ensures all duplicate values are included.

Reverse Sorted List

A reverse sorted list represents one of the most disordered possible inputs. Some naive sorting algorithms perform poorly on this pattern. Merge sort still guarantees O(n log n) performance because its runtime depends only on recursive splitting and merging, not initial ordering.

Odd Length Lists

Lists with an odd number of nodes can produce uneven splits. The slow and fast pointer approach naturally handles this by placing the extra node into one half. Recursive sorting still works correctly because each half eventually reaches the base case.