Domain 2MediumCORE

Sort List

We are given the head of a singly linked list and need to return that same structure sorted in ascending order. The input is head, which can be null, representing an empty list. We must preserve the node objects themselves (in-place sorting) rather than creating new nodes for every element.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Linked List#Sort

148. Sort List

Model: qwen3.5:9b
Topics: Linked List,Sort
FAANG asked: 1
Acceptance rate: 46.7%


Problem Breakdown

We are given the head of a singly linked list and need to return that same structure sorted in ascending order. The input is head, which can be null, representing an empty list. We must preserve the node objects themselves (in-place sorting) rather than creating new nodes for every element.

Key constraints:

  1. Memory: The follow-up explicitly asks for O(1)O(1) extra memory usage relative to the number of elements in the input structure. This rules out converting to an array or using a heap sort that requires random access indices (which effectively uses auxiliary space).
  2. Time: With NN up to 5×1045 \times 10^4, we need better than quadratic time complexity (O(N2)O(N^2)) for the worst case, as insertion sort would fail here.
  3. Edge Cases: Empty list (None), single node (already sorted), duplicates, and negative values must be handled correctly by our comparison logic.

Intuition

If we treat this like an array problem, QuickSort is O(Nlog⁡N)O(N \log N) on average but degrades to O(N2)O(N^2) worst-case without careful pivot selection, plus it requires random access which linked lists lack (O(1)O(1) index lookup). Heap Sort also typically relies on indexing.

The standard algorithm for sorting a singly linked list efficiently in terms of space is Merge Sort. Why?

  1. Splitting: We can split the list into two halves using the “Fast and Slow Pointer” technique to find the middle node without traversing twice or allocating extra memory. This takes O(N)O(N) time but only uses pointers (O(1))O(1)).
  2. Merging: Merging two sorted linked lists is a linear pass through both sub-lists, requiring no auxiliary arrays—just pointer manipulation.
  3. Recursion Depth: The recursion depth will be proportional to the height of the tree we build during sorting, which for Merge Sort is log⁡N\log N. While this uses stack space (O(log⁡N)O(\log N)), it does not use heap memory (like an array buffer). In interview contexts, O(Nlog⁡N)O(N \log N) time and “constant” auxiliary data structures usually refers to excluding recursion stack or treating the input structure’s nodes as free.

Approach

  1. Base Case: If head is null or has only one node (head.next is None), return head. The list is already sorted.
  2. Divide (Split): Use two pointers: a slow pointer moving at speed xx and a fast pointer moving at speed 2x2x. When the fast pointer hits the end, the slow pointer will be at the middle of the current segment. Break the link there (slow.next = None) to separate left and right sub-lists.
  3. Conquer (Recurse): Recursively call sortList on both halves until they are base cases.
  4. Combine (Merge): Implement a standard merge function that takes two sorted lists, compares their heads, appends the smaller value to a dummy node’s tail, and advances pointers accordingly. Return the head of the merged list.

Complexity Analysis

  • Time: O(Nlog⁡N)O(N \log N). The recurrence relation is T(N)=2T(N/2)+O(N)T(N) = 2T(N/2) + O(N) (splitting takes constant time if we count pointer movement as part of merge, or linear to find mid). Merging two lists of size NN takes O(N)O(N). By the Master Theorem, this resolves to O(Nlog⁡N)O(N \log N).
  • Space:
    • Auxiliary Space: O(1)O(1) excluding recursion stack. We only use pointers for splitting and merging; no arrays or hash maps are allocated.
    • Stack Space: O(log⁡N)O(\log N) due to the recursive calls in Merge Sort (depth of a balanced binary tree). This is standard for this problem’s follow-up requirements unless an iterative merge sort implementation is explicitly demanded, which significantly increases code complexity without practical benefit here.

Solution

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

def sortList(head):
    # Base case: empty list or single node is already sorted
    if not head or not head.next:
        return head
    
    # Step 1: Split the list into two halves using Fast/Slow pointers
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
    mid = slow.next
    slow.next = None  # Break the link to separate left and right
    
    # Step 2: Recursively sort both halves
    left_sorted = sortList(head)
    right_sorted = sortList(mid)
    
    # Step 3: Merge the two sorted halves
    return merge(left_sorted, right_sorted)

def merge(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
        
    # Append remaining nodes (one list will be exhausted)
    if l1:
        curr.next = l1
    elif l2:
        curr.next = l2
        
    return dummy.next

# Helper to run locally without full class definition overhead in snippet context 
if __name__ == "__main__":
    # Example usage logic would go here, but function is the core deliverable.

Edge Cases Handled

  • Empty List (head is None): The base case not head returns immediately without error.
  • Single Node: Base case not head.next handles this; recursion depth 1 or 0, merge loop runs once with one list exhausted instantly.
  • Duplicates: Merge logic uses l1.val <= l2.val, ensuring stability (preserving relative order of equal elements) and correct placement without skipping duplicates.
  • Negative Values: Comparison operators (<=) work correctly for negative integers in Python, so no special handling is required beyond standard integer comparison.