Problem Description

You are given the head of a singly linked list. Your task is to sort this linked list using the insertion sort algorithm and return the head of the sorted list.

How Insertion Sort Works:

Insertion sort builds the final sorted list one element at a time. It works similarly to how you might sort playing cards in your hands:

1. Start with an empty sorted portion (or consider the first element as already sorted)
2. Take one element from the unsorted portion
3. Find the correct position in the sorted portion where this element should be inserted
4. Insert the element at that position
5. Repeat until all elements are processed

For a Linked List:

• Initially, consider the first node as the sorted portion
• For each subsequent node:
  • Remove it from its current position
  • Traverse the sorted portion from the beginning to find where it belongs
  • Insert it at the correct position to maintain sorted order
  • Continue with the next unsorted node

Example: If the input linked list is 4 -> 2 -> 1 -> 3, the sorting process would be:

• Start: 4 (sorted) | 2 -> 1 -> 3 (unsorted)
• Step 1: Insert 2 → 2 -> 4 (sorted) | 1 -> 3 (unsorted)
• Step 2: Insert 1 → 1 -> 2 -> 4 (sorted) | 3 (unsorted)
• Step 3: Insert 3 → 1 -> 2 -> 3 -> 4 (sorted)

The algorithm maintains the linked list structure while rearranging the nodes to achieve sorted order based on their values in ascending order.

Intuition

When implementing insertion sort on a linked list, we need to think about how to efficiently manage node connections while sorting. Unlike arrays where we shift elements, in linked lists we manipulate pointers.

The key insight is to use a dummy node at the beginning of our sorted portion. This dummy node serves as an anchor point that simplifies our insertion logic - we never have to worry about updating the head of the list separately.

Here's the thought process:

1. Why check if pre.val <= cur.val? If the current node is already in the correct position (greater than or equal to the previous node), we don't need to move it. This optimization saves us from unnecessary traversal and pointer manipulation.

2. Finding the insertion point: When we need to move a node, we start from the dummy node and traverse the sorted portion until we find where cur belongs. We're looking for the spot where p.next.val > cur.val - this means cur should be inserted between p and p.next.

3. The pointer manipulation dance:

   • Save cur.next in a temporary variable t (we'll need this to continue iteration)
   • Insert cur into its new position by setting cur.next = p.next and p.next = cur
   • Fix the gap left by removing cur by setting pre.next = t
   • Move to the next unsorted node by setting cur = t

The beauty of this approach is that we're building our sorted list in-place. We're not creating new nodes - just rearranging the existing ones. The dummy node eliminates edge cases when inserting at the beginning, and by maintaining a pre pointer, we can efficiently remove nodes from their current position without losing track of where we are in the traversal.

Solution Approach

Let's walk through the implementation step by step:

Initial Setup:

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

First, we handle edge cases - if the list is empty or has only one node, it's already sorted.

dummy = ListNode(head.val, head)
pre, cur = dummy, head

We create a dummy node that points to the head. This dummy acts as a sentinel before our sorted portion. We initialize two pointers:

• pre: tracks the last node in the sorted portion
• cur: points to the current node being processed

Main Sorting Loop:

while cur:

We iterate through each node in the original list.

Optimization Check:

if pre.val <= cur.val:
    pre, cur = cur, cur.next
    continue

If the current node is already in the correct position (greater than or equal to the previous node), we simply advance both pointers. This is an important optimization that keeps already-sorted sequences intact.

Finding Insertion Position:

p = dummy
while p.next.val <= cur.val:
    p = p.next

When we need to move a node, we start from the dummy node and traverse the sorted portion. We stop when p.next.val > cur.val, meaning cur should be inserted between p and p.next.

Pointer Manipulation:

t = cur.next          # Save the next node to process
cur.next = p.next     # Insert cur after p
p.next = cur          # Complete the insertion
pre.next = t          # Remove cur from its old position
cur = t               # Move to the next unsorted node

This sequence carefully:

1. Saves the reference to the next unsorted node (t)
2. Inserts cur into its correct position in the sorted portion
3. Patches the gap left by removing cur from its original position
4. Moves to process the next node

Return Result:

return dummy.next

Since our dummy node has the same value as the original head, dummy.next points to the actual head of our sorted list.

Time Complexity: O(n²) - In the worst case (reverse sorted list), for each of the n nodes, we might traverse up to n nodes to find the insertion position.

Space Complexity: O(1) - We only use a constant amount of extra space for pointers and the dummy node.

Example Walkthrough

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

Initial State:

• Create dummy node with value 3, pointing to head
• dummy -> 3 -> 1 -> 4 -> 2
• pre = dummy, cur = 3 (first node)

Iteration 1: Process node 3

• Check: Is pre.val (3) <= cur.val (3)? Yes!
• No movement needed, advance pointers
• pre = 3, cur = 1
• List unchanged: 3 -> 1 -> 4 -> 2

Iteration 2: Process node 1

• Check: Is pre.val (3) <= cur.val (1)? No, need to move 1
• Find insertion position: Start at dummy, traverse while p.next.val <= 1
  • p = dummy, check p.next.val (3) <= 1? No, stop here
  • Insert 1 after dummy (before 3)
• Pointer manipulation:
  • t = 4 (save next node)
  • 1.next = 3 (insert 1 before 3)
  • dummy.next = 1 (dummy points to 1)
  • 3.next = 4 (fix the gap)
  • cur = 4 (move to next)
• List becomes: 1 -> 3 -> 4 -> 2

Iteration 3: Process node 4

• Check: Is pre.val (3) <= cur.val (4)? Yes!
• No movement needed, advance pointers
• pre = 4, cur = 2
• List unchanged: 1 -> 3 -> 4 -> 2

Iteration 4: Process node 2

• Check: Is pre.val (4) <= cur.val (2)? No, need to move 2
• Find insertion position: Start at dummy, traverse while p.next.val <= 2
  • p = dummy, check p.next.val (1) <= 2? Yes, continue
  • p = 1, check p.next.val (3) <= 2? No, stop here
  • Insert 2 between 1 and 3
• Pointer manipulation:
  • t = None (no next node)
  • 2.next = 3 (insert 2 before 3)
  • 1.next = 2 (1 points to 2)
  • 4.next = None (fix the gap)
  • cur = None (done)
• List becomes: 1 -> 2 -> 3 -> 4

Final Result: Return dummy.next which points to 1, giving us the sorted list 1 -> 2 -> 3 -> 4

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm implements insertion sort on a linked list. In the worst case (when the list is sorted in reverse order), for each node we need to:

• Traverse from the dummy node to find the correct insertion position
• For the i-th node, we may need to traverse up to i nodes to find the insertion point
• This results in 1 + 2 + 3 + ... + n = n(n+1)/2 operations
• Therefore, the time complexity is O(n²)

In the best case (when the list is already sorted), the condition pre.val <= cur.val is always true, so we simply traverse the list once, giving O(n) time complexity. However, we consider the worst-case for Big-O notation.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• A dummy node created at the beginning
• A few pointer variables (pre, cur, p, t)
• No additional data structures that scale with input size
• The sorting is done in-place by rearranging the existing nodes

Therefore, the space complexity is O(1) (constant space).

Common Pitfalls

Pitfall 1: Incorrect Dummy Node Initialization

Problem: The original code uses ListNode(head.val, head) to create the dummy node. This creates a duplicate node with the same value as the head, which becomes part of the final list and causes incorrect results.

Why it happens: The constructor ListNode(head.val, head) creates a new node with head.val as its value and head as its next pointer. This means you're adding an extra node to your list rather than just creating a sentinel.

Correct approach:

# Wrong
dummy = ListNode(head.val, head)

# Correct
dummy = ListNode(float('-inf'))  # or any value less than all possible node values
dummy.next = head

Pitfall 2: Not Handling the Boundary Between Sorted and Unsorted Portions

Problem: When moving a node from the unsorted portion to the sorted portion, failing to properly update the prev pointer can lead to losing track of where the sorted portion ends.

Example scenario: If you insert a node into the sorted portion but don't maintain prev correctly, you might process the same nodes multiple times or skip nodes.

Solution: After inserting a node, prev should remain pointing to the last node that was naturally in order (not moved). Don't update prev when you move a node backward.

Pitfall 3: Infinite Loop Due to Incorrect Pointer Updates

Problem: If the pointer manipulation sequence is wrong, you might create cycles in the linked list or lose references to parts of the list.

Common mistake:

# Wrong order - creates potential issues
cur.next = p.next     
pre.next = cur.next   # This now points to p.next, not the original cur.next!
p.next = cur

Correct sequence:

# Save next node first
next_node = cur.next
# Remove cur from current position
pre.next = next_node
# Insert cur in new position
cur.next = p.next
p.next = cur
# Update cur for next iteration
cur = next_node

Pitfall 4: Comparison Logic Error in Finding Insert Position

Problem: Using <= instead of < when finding the insertion position can cause duplicate values to be placed in the wrong order or create an infinite loop.

Why it matters: For stable sorting (maintaining relative order of equal elements), you should insert equal elements after existing equal elements, not before them.

# Potentially problematic for duplicates
while p.next.val <= cur.val:  # might skip past equal values
    p = p.next

# Better for stability
while p.next and p.next.val < cur.val:  # stops at first equal or greater value
    p = p.next

Pitfall 5: Forgetting to Check for Null Before Accessing Values

Problem: When traversing to find the insertion position, forgetting to check if p.next exists before accessing p.next.val causes null pointer exceptions.

Fix:

# Add null check
while p.next and p.next.val < cur.val:
    p = p.next

These pitfalls are particularly tricky because they might work for some test cases but fail on edge cases like lists with duplicate values, already sorted lists, or single-element lists.