206. Reverse Linked List - Detailed Explanation

Problem statement

Given the head of a singly linked list, reverse the list and return the reversed list.

In other words, you need to change the next pointers of all the nodes so that the list is reversed.

This question defines the In-place Reversal of a Linked List pattern, the technique that redirects existing next pointers one at a time instead of building a second list. Interviewers use it as the base case for every harder list question, and it is one of the recurring coding interview patterns worth drilling early. It also sits on the Blind 75 list.

Example inputs and outputs

• Example 1:

  • Input: head = [1, 2, 3, 4, 5]
  • Output: [5, 4, 3, 2, 1]
  • Explanation:
    The linked list is reversed so that the new head is the node with value 5, followed by nodes with values 4, 3, 2, and 1.

• Example 2:

  • Input: head = [1, 2]
  • Output: [2, 1]
  • Explanation:
    The two nodes swap positions.

• Example 3:

  • Input: head = []
  • Output: []
  • Explanation:
    An empty list remains empty after reversal.

Hints

1. Iterative approach using pointers:
   Think about maintaining two pointers, one for the previous node and one for the current node. As you traverse the list, you point the next pointer of the current node back at the previous node.

2. Recursive approach:
   The recursive solution reverses the rest of the list first, then repairs the pointer of the current node.

Approaches

1. Iterative approach

Idea:

• Initialize two pointers: prev (set to None) and curr (set to the head).
• Traverse the list and for each node:
  • Save the next node.
  • Point the next pointer of the current node back at the previous node.
  • Move the prev and curr pointers one step forward.
• Return prev as the new head when curr becomes None.

Steps:

1. Set prev = None and curr = head.
2. While curr is not None:
   • Temporarily store curr.next.
   • Set curr.next to prev, which reverses the link.
   • Move prev to curr and curr to the stored next node.
3. Return prev as the head of the reversed list.

2. Recursive approach

Idea:

• The base case is an empty list or a list with one node.
• Recursively reverse the sublist starting from the second node.
• Adjust the pointers so that the next node points back to the current node. Then set the next pointer of the current node to None.

Steps:

1. If head is None or head.next is None, return head.
2. Otherwise, recursively reverse the list from head.next onward.
3. Set head.next.next to head to reverse the link.
4. Set head.next to None to break the original link.
5. Return the new head from the recursive call.

Code implementations

Python code