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:
- Memory: The follow-up explicitly asks for 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).
- Time: With up to , we need better than quadratic time complexity () for the worst case, as insertion sort would fail here.
- 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 on average but degrades to worst-case without careful pivot selection, plus it requires random access which linked lists lack ( 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?
- 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 time but only uses pointers (.
- Merging: Merging two sorted linked lists is a linear pass through both sub-lists, requiring no auxiliary arrays—just pointer manipulation.
- Recursion Depth: The recursion depth will be proportional to the height of the tree we build during sorting, which for Merge Sort is . While this uses stack space (), it does not use heap memory (like an array buffer). In interview contexts, time and “constant” auxiliary data structures usually refers to excluding recursion stack or treating the input structure’s nodes as free.
Approach
- Base Case: If
headis null or has only one node (head.nextis None), returnhead. The list is already sorted. - Divide (Split): Use two pointers: a slow pointer moving at speed and a fast pointer moving at speed . 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. - Conquer (Recurse): Recursively call
sortListon both halves until they are base cases. - 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: . The recurrence relation is (splitting takes constant time if we count pointer movement as part of merge, or linear to find mid). Merging two lists of size takes . By the Master Theorem, this resolves to .
- Space:
- Auxiliary Space: excluding recursion stack. We only use pointers for splitting and merging; no arrays or hash maps are allocated.
- Stack Space: 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 (
headis None): The base casenot headreturns immediately without error. - Single Node: Base case
not head.nexthandles 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.