Reverse a Doubly Linked List
The problem discussed here involves reversing a doubly linked list. A doubly linked list is a data structure where each node contains a value and two pointers, one pointing to the next node (in the forward direction) and another pointing to the previous node (in the backward direction). The task is to reverse the order of the nodes in the linked list while preserving the connections between them.


Problem Statement
Given a doubly linked list, the objective is to reverse the order of the nodes, changing the head to point to the previously last node and the tail to point to the previously first node.
Idea to Solve
The idea to solve this problem is to iterate through the linked list while reversing the connections of each node. For each node, swap its next and prev pointers to reverse the order. Also, update the head and tail pointers accordingly.
Pseudocode
Here's the pseudocode that outlines the algorithm to reverse a doubly linked list:
class LinkNode:
int data
LinkNode next
LinkNode prev
class DoublyLinkedList:
LinkNode head
LinkNode tail
function reverse():
If head is null:
Print "Empty Linked List"
Else:
Initialize temp node with head
Initialize back node with null
Update tail to head
While temp is not null:
Update head to temp
Move temp to temp's next
Update temp's prev to temp's next
Update temp's next to back
Update back to temp
Create a DoublyLinkedList object
Insert nodes into the object
Display the linked list
Call reverse function to reverse the linked list
Display the reversed linked list
Algorithm Explanation
- The
reverse
function checks if the list is empty. If it is, it prints "Empty Linked List." Otherwise, it initializes a temp node with the head and a back node with null. It also updates the tail pointer to point to the head since the tail will become the new head after reversing. - The algorithm iterates through the linked list. For each node, it swaps the next and prev pointers to reverse the connections. It also updates the head pointer to the current node and moves the temp pointer to the next node. The back pointer is used to store the previous node in the reversed order.
- After the loop, the reversed list is constructed, and both the head-to-tail and tail-to-head connections are reversed.
Code Solution
-
1) Reverse doubly linked list in java
2) Reverse doubly linked list in c++
3) Reverse doubly linked list in c
4) Reverse doubly linked list in golang
5) Reverse doubly linked list in c#
6) Reverse doubly linked list in vb.net
7) Reverse doubly linked list in php
8) Reverse doubly linked list in node js
9) Reverse doubly linked list in typescript
10) Reverse doubly linked list in python
11) Reverse doubly linked list in ruby
12) Reverse doubly linked list in scala
13) Reverse doubly linked list in swift
14) Reverse doubly linked list in kotlin
Time Complexity
- Reversing a doubly linked list requires visiting each node once, so the time complexity is O(N), where N is the number of nodes in the linked list.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment