Problem Description

You are given the head of a singly linked list. Your task is to reverse the entire linked list and return the head of the reversed list.

In a singly linked list, each node contains a value and a pointer to the next node. The reversal means that all the arrows pointing from one node to the next should be flipped in the opposite direction.

For example:

• If the original list is: 1 -> 2 -> 3 -> 4 -> 5
• The reversed list should be: 5 -> 4 -> 3 -> 2 -> 1

The solution uses a head insertion technique with a dummy node. Here's how it works:

1. Create a dummy node that will serve as a temporary head
2. Traverse through the original list one node at a time
3. For each node visited:
   • Save the reference to the next node in the original list
   • Insert the current node right after the dummy node (at the beginning of the new list)
   • Move to the saved next node
4. After processing all nodes, dummy.next points to the new head of the reversed list

The key insight is that by always inserting nodes right after the dummy node, we naturally build the list in reverse order. Each new node becomes the new first node of the reversed portion.

Intuition

When we need to reverse a linked list, we essentially want to flip all the arrows between nodes. The challenge is that in a singly linked list, we can only traverse forward, and once we change a node's next pointer, we lose access to the rest of the original list.

Think about how you would reverse a stack of papers: you'd take papers from the top of the original stack and place them one by one onto a new stack. The first paper from the original becomes the last in the new stack, and the last paper from the original becomes the first in the new stack.

We can apply a similar principle here using a "head insertion" strategy. Imagine we have a new empty list (represented by a dummy node), and we want to build the reversed list by always adding nodes at the beginning of this new list.

As we traverse the original list from head to tail:

• The first node we encounter (originally at position 1) gets inserted at the front of our new list
• The second node (originally at position 2) also gets inserted at the front, pushing the first node to position 2
• This continues, with each subsequent node pushing all previous nodes one position back

By consistently inserting at the head position, we naturally achieve the reversal. The last node we process (the tail of the original list) ends up at the front of our new list, becoming the new head.

The dummy node technique is particularly elegant here because it eliminates edge cases. We don't need special handling for an empty list or the first node - the dummy node provides a consistent anchor point where dummy.next always points to the current head of our reversed portion.

Solution Approach

The implementation uses the head insertion method with a dummy node to reverse the linked list. Let's walk through the algorithm step by step:

Initial Setup:

• Create a dummy node with dummy = ListNode(). This node serves as a placeholder before the head of our reversed list
• Set curr = head to start traversing from the beginning of the original list

Main Reversal Loop: The while curr: loop continues until we've processed all nodes:

1. Save the next node: next = curr.next

   • We must save the reference to the next node before modifying any pointers, otherwise we'd lose access to the rest of the original list

2. Insert current node at the head: curr.next = dummy.next

   • Point the current node's next to whatever is currently after the dummy node (initially None, then the previously inserted nodes)

3. Update dummy to point to current: dummy.next = curr

   • Make the dummy node point to the current node, effectively placing it at the beginning of our reversed list

4. Move to the next node: curr = next

   • Advance to the saved next node to continue the traversal

Return the result: After the loop completes, dummy.next points to the head of the fully reversed list.

Example walkthrough with list 1 -> 2 -> 3:

• Initially: dummy -> None, curr = 1
• Iteration 1: Insert node 1 → dummy -> 1 -> None, curr = 2
• Iteration 2: Insert node 2 → dummy -> 2 -> 1 -> None, curr = 3
• Iteration 3: Insert node 3 → dummy -> 3 -> 2 -> 1 -> None, curr = None
• Return dummy.next which points to node 3 (the new head)

The time complexity is O(n) where n is the number of nodes, as we visit each node exactly once. The space complexity is O(1) since we only use a constant amount of extra space regardless of the input size.

Example Walkthrough

Let's walk through reversing the linked list 1 -> 2 -> 3 using the head insertion approach:

Initial State:

• Original list: 1 -> 2 -> 3 -> None
• Create dummy node: dummy -> None
• Set curr = 1 (pointing to first node)

Iteration 1: Processing Node 1

• Save next: next = 2 (save reference to node 2)
• Insert node 1 after dummy:
  • curr.next = dummy.next → Node 1 now points to None
  • dummy.next = curr → Dummy now points to node 1
• Result: dummy -> 1 -> None
• Move forward: curr = 2

Iteration 2: Processing Node 2

• Save next: next = 3 (save reference to node 3)
• Insert node 2 after dummy:
  • curr.next = dummy.next → Node 2 now points to node 1
  • dummy.next = curr → Dummy now points to node 2
• Result: dummy -> 2 -> 1 -> None
• Move forward: curr = 3

Iteration 3: Processing Node 3

• Save next: next = None (node 3 has no next)
• Insert node 3 after dummy:
  • curr.next = dummy.next → Node 3 now points to node 2
  • dummy.next = curr → Dummy now points to node 3
• Result: dummy -> 3 -> 2 -> 1 -> None
• Move forward: curr = None

Final Result:

• Loop ends since curr = None
• Return dummy.next which points to node 3
• Reversed list: 3 -> 2 -> 1 -> None

Notice how each node gets inserted at the front (right after dummy), naturally building the list in reverse order. The first node processed (1) ends up at the tail, while the last node processed (3) becomes the new head.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the linked list. This is because the algorithm uses a single while loop that traverses through each node in the linked list exactly once. Each operation inside the loop (pointer reassignment) takes constant time O(1), and since we visit all n nodes, the total time complexity is O(n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of the input size. It creates one dummy node and uses two pointer variables (curr and next) to track positions during the reversal process. These variables do not scale with the size of the input linked list, hence the constant space complexity.

Common Pitfalls

1. Losing the reference to the remaining list

One of the most frequent mistakes when reversing a linked list is forgetting to save the reference to the next node before modifying pointers. This leads to losing access to the rest of the original list.

Incorrect approach:

while current:
    current.next = dummy_node.next  # Oops! We just lost the original current.next
    dummy_node.next = current
    current = current.next  # This now points to dummy_node.next, not the original next node!

This creates an infinite loop or incorrect traversal because current.next has been modified before we saved its original value.

Correct approach:

while current:
    next_node = current.next  # Save the reference FIRST
    current.next = dummy_node.next
    dummy_node.next = current
    current = next_node  # Use the saved reference

2. Confusing the order of pointer updates

Another common mistake is updating the pointers in the wrong order, which can create cycles or break the list structure.

Incorrect approach:

while current:
    next_node = current.next
    dummy_node.next = current  # Setting this first
    current.next = dummy_node.next  # Now current.next points to itself!
    current = next_node

This creates a self-loop because dummy_node.next is already pointing to current when we set current.next = dummy_node.next.

Correct approach:

while current:
    next_node = current.next
    current.next = dummy_node.next  # First: point current to the existing reversed portion
    dummy_node.next = current  # Then: make dummy point to current
    current = next_node

3. Not handling edge cases properly

Forgetting to handle empty lists or single-node lists can cause issues, though the dummy node approach naturally handles these cases well.

Potential issue without proper initialization:

def reverseList(self, head: ListNode) -> ListNode:
    if not head:  # Unnecessary check with dummy node approach
        return None
    dummy_node = ListNode()
    # ... rest of code

Better approach (as in the solution): The dummy node approach elegantly handles all edge cases:

• Empty list: The while loop never executes, returns dummy_node.next which is None
• Single node: Loop executes once, correctly returns that single node
• Multiple nodes: Works as expected

The beauty of the dummy node approach is that it treats all cases uniformly without special handling.