LinkedListProblem 20 of 36
Reverse a Doubly Linked list
Reverse a Doubly Linked List
Problem Statement
Given a doubly linked list, reverse it in-place. The reversed list should have all the prev and next pointers correctly pointing to their new neighbors.
Example
Input: NULL <- 1 <-> 2 <-> 3 <-> 4 <-> 5 -> NULL
Output: NULL <- 5 <-> 4 <-> 3 <-> 2 <-> 1 -> NULL
Input: NULL <- 1 <-> 2 -> NULL
Output: NULL <- 2 <-> 1 -> NULL
Brute Force Approach
Intuition
The brute force approach involves storing all node values in a stack (or array), then traversing the list again and replacing values from the stack. This effectively reverses the order of values without changing the structure.
Algorithm
- Traverse the doubly linked list and push all values onto a stack
- Traverse the list again from the head
- Pop values from the stack and assign them to each node
- Return the head (structure unchanged, only values reversed)
Code
java
import java.util.Stack;
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class DoublyLinkedList {
public static Node reverseDLLBruteForce(Node head) {
if (head == null || head.next == null) {
return head;
}
Stack<Integer> stack = new Stack<>();
Node temp = head;
// Push all values to stack
while (temp != null) {
stack.push(temp.data);
temp = temp.next;
}
// Pop and assign values
temp = head;
while (temp != null) {
temp.data = stack.pop();
temp = temp.next;
}
return head;
}
public static void printList(Node head) {
Node temp = head;
System.out.print("NULL <- ");
while (temp != null) {
System.out.print(temp.data);
if (temp.next != null) {
System.out.print(" <-> ");
}
temp = temp.next;
}
System.out.println(" -> NULL");
}
}Complexity Analysis
- Time Complexity: O(n) - Two passes through the list
- Space Complexity: O(n) - Stack to store all values
Optimal Approach
Intuition
The optimal approach leverages the doubly linked list property - each node already has a prev pointer. We simply need to swap the prev and next pointers for every node. The key insight is that swapping these pointers for all nodes effectively reverses the list.
Algorithm
- Initialize current pointer to head
- For each node, swap its prev and next pointers
- Move to the next node (which is now prev after swapping)
- The new head is the last node we processed (when current becomes null, prev holds the new head)
Code
java
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class DoublyLinkedListOptimal {
public static Node reverseDLLOptimal(Node head) {
if (head == null || head.next == null) {
return head;
}
Node current = head;
Node temp = null;
// Swap prev and next for all nodes
while (current != null) {
// Swap prev and next
temp = current.prev;
current.prev = current.next;
current.next = temp;
// Move to next node (which is now prev)
current = current.prev;
}
// Return new head
return temp.prev;
}
public static void printList(Node head) {
Node temp = head;
System.out.print("NULL <- ");
while (temp != null) {
System.out.print(temp.data);
if (temp.next != null) {
System.out.print(" <-> ");
}
temp = temp.next;
}
System.out.println(" -> NULL");
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass through the list
- Space Complexity: O(1) - Only using constant extra space
Key Takeaways
- Leverage DLL Property: The doubly linked list already has prev pointers, making reversal simpler than singly linked list
- Swap Technique: Simply swapping prev and next pointers for each node reverses the list
- Pointer Tracking: After swapping, the "next" node is accessed through the prev pointer (since they're swapped)
- New Head Identification: The new head is the original tail - track it carefully after the loop
- In-place Reversal: The optimal solution modifies the list structure rather than just the values, which is the true reversal