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.

Example Inputs & 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 reverse the next pointer of the current node to point to the previous node.

2. Recursive Approach:
   The recursive solution involves reversing the rest of the list and then fixing the current node’s pointer.

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.
  • Reverse the pointer of the current node to point to 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 (reverse the pointer).
   • 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 when the list is empty or has 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, and then set the current node’s next 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