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 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.

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.
Recursive Approach:
The recursive solution involves reversing the rest of the list and then fixing the current node’s pointer.

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:

Set prev = None and curr = head.
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.
Return prev as the head of the reversed list.

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:

Python3

. . . .

Java

. . . .

Time Complexity:
- Both the iterative and recursive approaches traverse each node exactly once, so the time complexity is O(n), where n is the number of nodes in the list.
Space Complexity:
- Iterative Approach: Uses constant extra space, O(1).
- Recursive Approach: Uses O(n) space in the recursion stack.

Initialization:
Set prev = None and curr = head (the first node of the list).
Iteration:
- While curr is not null:
  - Save curr.next in a temporary variable (next_temp).
  - Change curr.next to point to prev, effectively reversing the pointer.
  - Move prev to curr and curr to next_temp.
Termination:
When curr becomes null, prev points to the new head of the reversed list.
Return:
Return prev as the head of the reversed linked list.

Losing the Next Node:
Not saving curr.next before changing curr.next leads to losing access to the rest of the list.
Incorrect Pointer Updates:
Updating pointers in the wrong order may result in a broken list or an infinite loop.
Forgetting to Handle Empty Lists:
Ensure that the algorithm correctly returns None or an empty list when the input is empty.

Edge Cases:
- Empty List:
  If the input list is empty, simply return None.
- Single Node:
  A list with one node should remain unchanged after reversal.
Alternative Variations:
- Partial Reversal:
  Problems that require reversing only a portion of the list.
- Reversing in Groups:
  Reversing nodes in groups (e.g., reverse every k nodes).

Reverse Nodes in k-Group:
Reverse nodes of a linked list in groups of size k.
Swap Nodes in Pairs:
Swap every two adjacent nodes in a linked list.
Linked List Cycle Detection:
Determine if a linked list has a cycle.

TAGS

leetcode

CONTRIBUTOR

Design Gurus Team