POTD Solutions | 18 Nov’ 23 | Reverse a Doubly Linked List
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Linked Lists but will also help you build up problem-solving skills.
POTD 18 November: Reverse a Doubly Linked List:
Given a doubly linked list of n elements. Your task is to reverse the doubly linked list in-place.
Examples:
Input: LinkedList: 3 <–> 4 <–> 5
Output: 5 <–> 4 <–> 3Input: LinkedList: 75 <–> 122 <–> 59 <–> 196
Output: 196 <–> 59 <–> 122 <–> 75
Reverse a Doubly Linked List by Iterative Approach:
The idea is to use an iterative approach. We can modify the prev and next pointers of each node to reverse the direction of the links.
Step-by-step approach:
- Initialize two pointers, curr and prev. Initially, curr points to the head of the list, and prev is set to null.
- Enter a loop that iterates through the entire list. Inside the loop:
- Update the curr node’s prev pointer to its next pointer, effectively reversing the direction of the link.
- Update the curr node’s next pointer to prev, again reversing the direction of the link.
- Essentially, the prev and next pointers are swapped to reverse the node’s connections in the DLL.
- Once the loop is complete, the curr pointer will be pointing to the new head of the reversed list, and the prev pointer will be pointing to the node that was originally at the end of the list (now the new tail). Return prev to indicate the new head of the reversed DLL.
Below is the implementation of the above approach:
C++
class Solution { public : // Function to reverse a doubly linked list Node* reverseDLL(Node * head) { // If the list is empty or has only one node, return the head if (head == NULL || head->next == NULL) return head; Node *prev = NULL, *curr = head; // Traverse through the list and swap the previous and next pointers while (curr != NULL){ prev = curr->prev; // Store the previous node curr->prev = curr->next; // Set the previous pointer to the next node curr->next = prev; // Set the next pointer to the previous node curr = curr->prev; // Move to the next node } return prev->prev; // Return the new head of the reversed list } }; |
Java
//Function to reverse a doubly linked list public static Node reverseDLL(Node head) { //checking if head is null or head.next is null, //if true, then return the head itself as there is no need to reverse a list with 0 or 1 node if (head == null || head.next == null ) return head; //declaring a current and previous node Node curr = head, prev = null ; //looping through the list while (curr != null ){ //storing the previous node in prev prev = curr.prev; //swapping the prev and next pointers of the current node curr.prev = curr.next; curr.next = prev; //moving the current node to its previous node curr = curr.prev; } //returning the previous node of head as the new head (the last node after reversing the list) return prev.prev; } |
Python3
class Solution: def reverseDLL( self , head): # Initialize temporary variables temp = None current = head # Reverse the doubly linked list while current is not None : # Swap previous and next pointers of the current node temp = current.prev current.prev = current. next current. next = temp current = current.prev # Update the head if necessary if temp is not None : head = temp.prev return head |
Time Complexity : O(N), where N is the number of nodes in the doubly linked list.
Auxiliary Space: O(1), constant space
Contact Us