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.