Reverse a Doubly Linked List
Problemβ
Given a doubly linked list of n elements, the task is to reverse this list in-place.
Examplesβ
Example 1:
Input:
LinkedList: 3 <--> 4 <--> 5
Output:
5 4 3
Explanation:
After reversing the list, elements are 5 <--> 4 <--> 3.
Example 2:
Input:
LinkedList: 75 <--> 122 <--> 59 <--> 196
Output:
196 59 122 75
Explanation:
After reversing the list, elements are 196 <--> 59 <--> 122 <--> 75.
Your Taskβ
Your task is to complete the given function reverseDLL()
, which takes head reference as an argument and reverses the elements in-place such that the tail becomes the new head and all pointers are pointing in the right order. You need to return the new head of the reversed list.
Expected Time Complexity:
Expected Auxiliary Space:
Constraintsβ
Solutionβ
Approachβ
To reverse a doubly linked list in-place, we can use three pointers: previous_node
, current_node
, and next_node
. The algorithm traverses the list, updating the pointers at each step until the entire list is reversed.
Python Codeβ
- Python
- Java
- C++
- JavaScript
- TypeScript
class Solution:
def reverseDLL(self, head):
while head:
head.next, head.prev = head.prev, head.next
if not head.prev:
return head
head = head.prev
class Solution {
public Node reverseDLL(Node head) {
while (head != null) {
Node temp = head.prev;
head.prev = head.next;
head.next = temp;
if (head.prev == null) {
return head;
}
head = head.prev;
}
return null;
}
}
class Solution {
public:
Node* reverseDLL(Node* head) {
while (head != nullptr) {
Node* temp = head->prev;
head->prev = head->next;
head->next = temp;
if (head->prev == nullptr) {
return head;
}
head = head->prev;
}
return nullptr;
}
};
class Solution {
reverseDLL(head) {
while (head) {
[head.next, head.prev] = [head.prev, head.next];
if (!head.prev) {
return head;
}
head = head.prev;
}
return null;
}
}
class Solution {
reverseDLL(head: Node): Node | null {
while (head) {
[head.next, head.prev] = [head.prev, head.next];
if (!head.prev) {
return head;
}
head = head.prev;
}
return null;
}
}
Complexity Analysisβ
- Time Complexity: where N is the number of elements in the doubly linked list. We traverse the entire list once.
- Space Complexity: , as we only use a constant amount of extra space for pointers.
Referencesβ
- GeeksforGeeks Problem: Reverse a Doubly Linked List
- Author GeeksforGeeks Profile: GeeksforGeeks