Given a Doubly Linked List, the task is to reverse the given Doubly Linked List.
See below diagrams for example.
[a] Original Doubly Linked ListHere is a simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers for all nodes, change prev of the head [or start] and change the head pointer in the end.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
#include using namespace std; class Node { public: int data; Node *next; Node *prev; }; void reverse[Node **head_ref] { Node *temp = NULL; Node *current = *head_ref; while [current != NULL] { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } if[temp != NULL ] *head_ref = temp->prev; } void push[Node** head_ref, int new_data] { Node* new_node = new Node[]; new_node->data = new_data; new_node->prev = NULL; new_node->next = [*head_ref]; if[[*head_ref] != NULL] [*head_ref]->prev = new_node ; [*head_ref] = new_node; } void printList[Node *node] { while[node != NULL] { cout data next; } } int main[] { Node* head = NULL; push[&head, 2]; push[&head, 4]; push[&head, 8]; push[&head, 10]; cout next = temp; current = current->prev; } if[temp != NULL ] *head_ref = temp->prev; } void push[struct Node** head_ref, int new_data] { struct Node* new_node = [struct Node*] malloc[sizeof[struct Node]]; new_node->data = new_data; new_node->prev = NULL; new_node->next = [*head_ref]; if[[*head_ref] != NULL] [*head_ref]->prev = new_node ; [*head_ref] = new_node; } void printList[struct Node *node] { while[node!=NULL] { printf["%d ", node->data]; node = node->next; } } int main[] { struct Node* head = NULL; push[&head, 2]; push[&head, 4]; push[&head, 8]; push[&head, 10]; printf["\n Original Linked list "]; printList[head]; reverse[&head]; printf["\n Reversed Linked list "]; printList[head]; getchar[]; } |
class LinkedList { static Node head; static class Node { int data; Node next, prev; Node[int d] { data = d; next = prev = null; } } void reverse[] { Node temp = null; Node current = head; while [current != null] { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } if [temp != null] { head = temp.prev; } } void push[int new_data] { Node new_node = new Node[new_data]; new_node.prev = null; new_node.next = head; if [head != null] { head.prev = new_node; } head = new_node; } void printList[Node node] { while [node != null] { System.out.print[node.data + " "]; node = node.next; } } public static void main[String[] args] { LinkedList list = new LinkedList[]; list.push[2]; list.push[4]; list.push[8]; list.push[10]; System.out.println["Original linked list "]; list.printList[head]; list.reverse[]; System.out.println[""]; System.out.println["The reversed Linked List is "]; list.printList[head]; } } |
class Node: def __init__[self, data]: self.data = data self.next = None self.prev = None class DoublyLinkedList: def __init__[self]: self.head = None def reverse[self]: temp = None current = self.head while current is not None: temp = current.prev current.prev = current.next current.next = temp current = current.prev if temp is not None: self.head = temp.prev def push[self, new_data]: new_node = Node[new_data] new_node.next = self.head if self.head is not None: self.head.prev = new_node self.head = new_node def printList[self, node]: while[node is not None]: print[node.data,end=' '] node = node.next dll = DoublyLinkedList[] dll.push[2] dll.push[4] dll.push[8] dll.push[10] print ["\nOriginal Linked List"] dll.printList[dll.head] dll.reverse[] print ["\nReversed Linked List"] dll.printList[dll.head] |
using System; public class LinkedList { static Node head; class Node { public int data; public Node next, prev; public Node[int d] { data = d; next = prev = null; } } void reverse[] { Node temp = null; Node current = head; while [current != null] { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } if [temp != null] { head = temp.prev; } } void push[int new_data] { Node new_node = new Node[new_data]; new_node.prev = null; new_node.next = head; if [head != null] { head.prev = new_node; } head = new_node; } void printList[Node node] { while [node != null] { Console.Write[node.data + " "]; node = node.next; } } public static void Main[String[] args] { LinkedList list = new LinkedList[]; list.push[2]; list.push[4]; list.push[8]; list.push[10]; Console.WriteLine["Original linked list "]; list.printList[head]; list.reverse[]; Console.WriteLine[""]; Console.WriteLine["The reversed Linked List is "]; list.printList[head]; } } |
var head; class Node { constructor[val] { this.data = val; this.prev = null; this.next = null; } } function reverse[] { var temp = null; var current = head; while [current != null] { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } if [temp != null] { head = temp.prev; } } function push[new_data] { var new_node = new Node[new_data]; new_node.prev = null; new_node.next = head; if [head != null] { head.prev = new_node; } head = new_node; } function printList[node] { while [node != null] { document.write[node.data + " "]; node = node.next; } } push[2]; push[4]; push[8]; push[10]; document.write["Original linked list printList[head]; reverse[]; document.write[" document.write["The reversed Linked List is printList[head]; |
Output:
Original linked list 10 8 4 2 The reversed Linked List is 2 4 8 10Time Complexity: O[N], where N denotes the number of nodes in the doubly linked list.
Auxiliary Space: O[1]
We can also swap data instead of pointers to reverse the Doubly Linked List. Method used for reversing array can be used to swap data. Swapping data can be costly compared to pointers if the size of the data item[s] is more.
Please write comments if you find any of the above codes/algorithms incorrect, or find better ways to solve the same problem.
Method 2:
The same question can also be done by using Stacks.
Steps:
- Keep pushing the node’s data in the stack. -> O[n]
- The keep popping the elements out and updating the Doubly Linked List
#include using namespace std; struct LinkedList { struct Node { int data; Node *next, *prev; Node[int d] { data = d; next = prev = NULL; } }; Node* head = NULL; void reverse[] { stack st; Node* temp = head; while [temp != NULL] { st.push[temp->data]; temp = temp->next; } temp = head; while [temp != NULL] { temp->data = st.top[]; st.pop[]; temp = temp->next; } } void Push[int new_data] { Node* new_node = new Node[new_data]; new_node->prev = NULL; new_node->next = head; if [head != NULL] { head->prev = new_node; } head = new_node; } void printList[Node* node] { while [node] { cout data next; } } }; int main[] { LinkedList list; list.Push[2]; list.Push[4]; list.Push[8]; list.Push[10]; cout Chủ Đề |