Problem Description

You are given the head of a linked list. Your task is to sort the linked list in ascending order based on the node values and return the head of the sorted list.

For example, if you have a linked list 4 -> 2 -> 1 -> 3, after sorting it should become 1 -> 2 -> 3 -> 4.

The solution uses a merge sort algorithm to efficiently sort the linked list. The approach works by:

1. Finding the middle point: Using the fast and slow pointer technique, where the slow pointer moves one step at a time while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle of the list.

2. Splitting the list: The linked list is divided into two halves at the middle point. The first half starts from head and ends at the node before slow.next, while the second half starts from slow.next.

3. Recursive sorting: Both halves (l1 and l2) are recursively sorted using the same approach until we have lists with only one node (which are inherently sorted).

4. Merging sorted lists: The two sorted halves are merged back together by comparing values. A dummy node is used to simplify the merging process. We iterate through both lists, always choosing the smaller value to append to our result list. After one list is exhausted, any remaining nodes from the other list are directly attached.

The base case for the recursion is when the list has zero or one node, which is already sorted and can be returned as-is.

The time complexity of this approach is O(n log n) where n is the number of nodes in the linked list, and the space complexity is O(log n) due to the recursive call stack.

Intuition

When we need to sort a linked list, we face a unique challenge compared to sorting arrays. In arrays, we can easily access any element by index in O(1) time, but in linked lists, we can only traverse sequentially. This makes many common sorting algorithms like quicksort less efficient for linked lists.

Merge sort becomes a natural choice for linked lists because:

1. No random access needed: Merge sort processes elements sequentially, which aligns perfectly with how we traverse linked lists.

2. Divide and conquer works well: We can split a linked list into two halves without needing extra space (unlike arrays where we'd need to copy elements). We just need to find the middle node and break the connection.

3. Merging is natural for linked lists: When merging two sorted linked lists, we simply adjust pointers rather than copying elements around. This is actually more efficient than merging arrays.

The key insight is using the fast and slow pointer technique to find the middle. Why does this work? If the fast pointer moves twice as fast as the slow pointer, when the fast pointer reaches the end, the slow pointer will have traveled exactly half the distance - landing us at the middle node.

The recursive nature of merge sort fits well here: keep breaking the problem into smaller pieces until we have lists of size 1 (which are trivially sorted), then build back up by merging. Each merge operation combines two already-sorted lists into one larger sorted list.

The beauty of this approach is that we're working with the natural structure of linked lists - following pointers and rearranging connections - rather than fighting against it by trying to access elements by position.

Solution Approach

The implementation follows the merge sort strategy outlined in the reference approach. Let's walk through the code step by step:

1. Base Case Check:

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

If the list is empty or has only one node, it's already sorted, so we return it immediately.

2. Finding the Middle Using Two Pointers:

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

We initialize slow at the head and fast at the second node (head.next). The fast pointer moves two steps while the slow pointer moves one step. When fast reaches the end, slow will be at the node just before the middle. This ensures we split the list correctly into two halves.

3. Splitting the List:

l1, l2 = head, slow.next
slow.next = None

• l1 starts from the head and goes up to the slow node
• l2 starts from slow.next and goes to the end
• We break the connection by setting slow.next = None, effectively creating two separate lists

4. Recursive Sorting:

l1, l2 = self.sortList(l1), self.sortList(l2)

We recursively sort both halves. This continues until we reach lists of size 1, which are inherently sorted.

5. Merging the Sorted Lists:

dummy = ListNode()
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 or l2
return dummy.next

• A dummy node is created to simplify the merging process (we don't need to handle the special case of the first node)
• tail keeps track of the last node in our merged list
• We compare values from both lists and attach the smaller one to our result
• After one list is exhausted, we attach any remaining nodes with tail.next = l1 or l2
• Finally, we return dummy.next, which is the head of our sorted list

The time complexity is O(n log n) where n is the number of nodes, as we divide the list log n times and merge takes O(n) time at each level. The space complexity is O(log n) due to the recursive call stack.

Example Walkthrough

Let's walk through sorting the linked list 4 -> 2 -> 1 -> 3 step by step.

Initial State: 4 -> 2 -> 1 -> 3

First Split (Level 1):

• Initialize pointers: slow = 4, fast = 2
• Move pointers: slow = 2, fast = 1 (fast moves to 1)
• Move again: slow stays at 2 since fast.next = 3 but fast.next.next = None
• Split into: l1 = 4 -> 2 (disconnect after 2) and l2 = 1 -> 3

Left Half Recursion (Level 2): 4 -> 2

• Initialize: slow = 4, fast = 2
• Since fast.next = None, loop doesn't execute
• Split into: l1 = 4 and l2 = 2
• Both are single nodes (base case), return as-is
• Merge: Compare 4 vs 2, pick 2 first, then 4
• Result: 2 -> 4

Right Half Recursion (Level 2): 1 -> 3

• Initialize: slow = 1, fast = 3
• Since fast.next = None, loop doesn't execute
• Split into: l1 = 1 and l2 = 3
• Both are single nodes (base case), return as-is
• Merge: Compare 1 vs 3, pick 1 first, then 3
• Result: 1 -> 3

Final Merge (Level 1): Now we merge 2 -> 4 and 1 -> 3:

• Create dummy node, tail = dummy
• Compare: 2 vs 1 → pick 1, tail.next = 1, advance to next in second list
• Compare: 2 vs 3 → pick 2, tail.next = 2, advance to next in first list
• Compare: 4 vs 3 → pick 3, tail.next = 3, advance to next in second list
• First list has 4 remaining, attach it: tail.next = 4
• Return dummy.next which points to: 1 -> 2 -> 3 -> 4

Final Result: 1 -> 2 -> 3 -> 4

The key insight is how the fast/slow pointer technique consistently finds the middle, allowing us to split the list evenly at each level, and how merging two sorted lists naturally produces a larger sorted list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm implements merge sort on a linked list. Breaking down the analysis:

• The list is recursively divided into halves log n times (similar to binary tree depth)
• At each level of recursion, all n nodes are processed during the merge operation
• The merge operation visits each node once to combine the sorted sublists
• Total operations: n nodes processed at each of log n levels = O(n × log n)

Space Complexity: O(log n)

The space complexity comes from the recursive call stack:

• The recursion depth is log n since we divide the list in half at each step
• Each recursive call uses O(1) additional space (only a few pointer variables like slow, fast, dummy, tail)
• No additional data structures are created; the sorting is done in-place by rearranging the existing nodes
• Total space: O(log n) for the call stack

The algorithm achieves optimal time complexity for comparison-based sorting while maintaining efficient space usage through in-place merging of the linked list nodes.

Common Pitfalls

1. Incorrect Middle Point Calculation

The Pitfall: A common mistake is initializing both slow and fast pointers at head:

# INCORRECT
slow = head
fast = head  # Wrong initialization
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

This causes the split to be uneven. For a list with 2 nodes, slow would end up at the second node, making l1 contain both nodes and l2 empty, leading to infinite recursion.

The Solution: Initialize fast at head.next:

# CORRECT
slow = head
fast = head.next  # Correct initialization
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

This ensures slow stops at the last node of the first half, allowing for a proper split.

2. Forgetting to Break the Connection

The Pitfall: After identifying the middle point, forgetting to set slow.next = None:

# INCORRECT
l1 = head
l2 = slow.next
# Missing: slow.next = None

Without breaking the connection, l1 would still point to the entire list, causing incorrect sorting or infinite loops.

The Solution: Always disconnect the two halves:

# CORRECT
l1 = head
l2 = slow.next
slow.next = None  # Critical step to separate the lists

3. Using Value Comparison Instead of Node Manipulation

The Pitfall: Creating new nodes instead of reusing existing ones during the merge:

# INCORRECT - Creates new nodes
while l1 and l2:
    if l1.val <= l2.val:
        tail.next = ListNode(l1.val)  # Creating new node
        l1 = l1.next
    else:
        tail.next = ListNode(l2.val)  # Creating new node
        l2 = l2.next
    tail = tail.next

This unnecessarily increases space complexity to O(n) and doesn't actually sort the original list.

The Solution: Reuse existing nodes by adjusting pointers:

# CORRECT - Reuses existing nodes
while l1 and l2:
    if l1.val <= l2.val:
        tail.next = l1  # Reuse existing node
        l1 = l1.next
    else:
        tail.next = l2  # Reuse existing node
        l2 = l2.next
    tail = tail.next

4. Edge Case Handling in Base Case

The Pitfall: Only checking for head is None without checking head.next is None:

# INCORRECT
if head is None:
    return head
# Missing check for single node

This misses the single-node case, which should also be treated as sorted.

The Solution: Check both empty and single-node cases:

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

These pitfalls often lead to infinite recursion, incorrect results, or runtime errors. The key is understanding that we're manipulating pointers to existing nodes rather than creating new structures.