Reverse a Doubly Linked List | GFG Practice | Iterative Solution

Given a doubly linked list. Your task is to reverse the doubly linked list and return its head.

Here’s the [Problem Link] to begin with.

Examples:

Input: LinkedList: 3 <-> 4 <-> 5
Output: 5 <-> 4 <-> 3

Input: LinkedList: 75 <-> 122 <-> 59 <-> 196
Output: 196 <-> 59 <-> 122 <-> 75

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).

Constraints:
1 <= number of nodes <= 10⁶
0 <= node->data <= 10⁴

Solution: Optimal Approach (Swap Pointers)

Intuition

Think of this like rearranging a train where each car is connected to both the car in front and behind it! To reverse the train’s direction, you need to swap the connections of each car – what used to be the “front” connection becomes the “back” connection, and vice versa. The key insight is that we don’t need to move the actual cars (nodes) – we just need to swap their connection directions. It’s like telling each car “your front is now your back, and your back is now your front!”

Detailed Approach

1. Handle Edge Cases: If the list is empty or has only one node, return it as is
2. Initialize Pointers: Set up current pointer to traverse and new_head to track the new head
3. Traverse and Swap: For each node, swap its prev and next pointers
4. Track New Head: Keep updating new_head to the current node (which will become the new head)
5. Move to Next: Move to the next node (which is actually the previous node after swapping)
6. Return New Head: The last node we processed becomes the new head

Code

class Solution:
    def reverseDLL(self, head):
        # Handle edge cases: empty list or single node
        if not head or not head.next:
            return head

        current = head      # Pointer to traverse through the list
        new_head = None     # Will store the new head after reversal

        # Traverse each node and swap prev and next pointers
        while current:
            # Store current.prev temporarily before swapping
            temp = current.prev
            
            # Swap the pointers: prev becomes next, next becomes prev
            current.prev = current.next
            current.next = temp

            # Update new_head to current node (last processed becomes new head)
            new_head = current

            # Move to the "next" node (which is actually current.prev after swap)
            current = current.prev

        return new_head

Code Explanation

This solution works by swapping the prev and next pointers of each node in the doubly linked list. We traverse through the list and for each node, we swap its connections so that what used to point forward now points backward, and vice versa. The clever part is that after swapping, we need to move to current.prev instead of current.next because the connections have been flipped. We keep track of the new head by updating it to each node we process – the last node we process will be the original tail, which becomes the new head.

Dry Run

Let’s trace through: 1 <-> 2 <-> 3 <-> 4

Initial Setup:

• current = 1, new_head = None
• Original: 1 <-> 2 <-> 3 <-> 4

Step 1: Process Node 1

• temp = None (1’s prev)
• Swap: 1.prev = 2, 1.next = None
• new_head = 1
• current = 1.prev = 2
• State: None <- 1 2 <-> 3 <-> 4

Step 2: Process Node 2

• temp = 1 (2’s prev)
• Swap: 2.prev = 3, 2.next = 1
• new_head = 2
• current = 2.prev = 3
• State: None <- 1 <- 2 3 <-> 4

Step 3: Process Node 3

• temp = 2 (3’s prev)
• Swap: 3.prev = 4, 3.next = 2
• new_head = 3
• current = 3.prev = 4
• State: None <- 1 <- 2 <- 3 4

Step 4: Process Node 4

• temp = 3 (4’s prev)
• Swap: 4.prev = None, 4.next = 3
• new_head = 4
• current = 4.prev = None
• State: None <- 1 <- 2 <- 3 <- 4

Final Result: 4 <-> 3 <-> 2 <-> 1 with new_head = 4

Time and Space Complexity

• Time Complexity: O(n) – We visit each node exactly once during traversal
• Space Complexity: O(1) – We only use a few pointer variables, no extra space needed

Simplifying It

This approach is like rearranging a chain of people holding hands where everyone can hold both the hand in front and behind them. To reverse the direction, you tell each person “switch hands” – whoever was on your left is now on your right, and vice versa. You don’t need to physically move anyone, just change who they’re holding hands with. The person who was at the end of the line naturally becomes the new leader!

Key Insights

Why we swap pointers instead of values:
Swapping pointers is more efficient than swapping values because we only need to change references, not copy actual data. This works regardless of how large the data in each node is.

Why we move to current.prev after swapping:
After swapping the pointers, the “next” node in our original direction is now accessible through the prev pointer. It’s like the directions got flipped!

Why we track new_head:
Since we’re changing the direction of the entire list, the original tail becomes the new head. We keep updating new_head so we know which node to return.

Summary

This optimal solution efficiently reverses the doubly linked list in a single pass using constant extra space. The key insight is that we don’t need to move nodes around – we just need to swap their connection directions.

This problem beautifully demonstrates the power of pointer manipulation in doubly linked lists. The bidirectional nature of doubly linked lists makes reversal elegant because we can simply swap the direction of each connection. It’s a fundamental operation that appears in many advanced algorithms and data structure problems!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.