Posted on by Kalkicode

# 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

function reverse():
Else:
Initialize back node with null
While temp is not null:
Move temp to temp's next
Update temp's prev to temp's next
Update temp's next to back
Update back to temp

Insert nodes into the object
Call reverse function to reverse the 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.

## 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.

## Comment

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.

Categories
Relative Post