Learn LinkedList [Single LL, Double LL]Doubly Linked List

Reverse a Doubly Linked List

JavaScript Solution & Complexity Analysis

Run & test in browser
JavaScript Lab Sandbox
/*
Problem Statement: Given a doubly linked list of size ‘N’ consisting of positive integers, your task is to reverse it and return the head of the modified doubly linked list.
*/

class Node {
    constructor(data, next = null, prev = null) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
};

class DoublyLinkedListClass {
    constructor() {
        this.head = null;
        this.prev = null;
    };

    insertAtTheStartOfDoublyLinkedList(value) {
        /*
        T.C - O(1)
        S.C - O(1)
        */
        const newNode = new Node(value);

        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            return;
        }

        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    };

    insertAtTheEndOfDoublyLinkedList(value) {
        /*
        T.C - O(N)
        S.C - O(1)
        */
        let newNode = new Node(value);
        if (!this.head) {
            return newNode;
        }
        let temp = this.head;
        while (temp.next) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
        return this.head;
    };

    deleteTheLastNodeOfDoublyLinkedList() {
        /*
        T.C - O(N)
        S.C - O(1)
        */
        if (this.head.next === null || this.head === null) {
            return null;
        }
        let temp = this.head;
        while (temp.next) {
            temp = temp.next;
        };
        temp.prev.next = null;
        return this.head;
    };

    reverseDoublyLinkedListBruteForceApproach() {
        /*
        T.C - O(N)
        S.C - O(N)
        */
        let temp1 = this.head, temp2 = this.head;
        let valueArray = [];
        while (temp1) {
            valueArray.push(temp1.data);
            temp1 = temp1.next;
        };
        while (temp2) {
            temp2.data = valueArray.pop();
            temp2 = temp2.next;
        }
        return this.head;
    };

    reverseDoublyLinkedListOptimisedApproach() {
        /*
        T.C - O(N)
        S.C - O(1)
        */
        let temp = null, current = this.head;
        while (current !== null) {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        };

        if (temp !== null) {
            this.head = temp.prev;
        }

        return this.head;
    }

    printDoublyLinkedList() {
        /*
        T.C - O(N)
        S.C - O(1)
        */
        let temp = this.head;
        while (temp !== null) {
            console.log(temp.data);
            temp = temp.next;
        };
    };
};

const DoublyLinkedList = new DoublyLinkedListClass();
DoublyLinkedList.insertAtTheStartOfDoublyLinkedList(10);
DoublyLinkedList.insertAtTheEndOfDoublyLinkedList(20);
DoublyLinkedList.insertAtTheEndOfDoublyLinkedList(30);
console.log("Doubly Linked List Before Deletion:");
DoublyLinkedList.printDoublyLinkedList();
console.log("Doubly Linked List After Deletion:");
DoublyLinkedList.deleteTheLastNodeOfDoublyLinkedList();
DoublyLinkedList.printDoublyLinkedList();
console.log("Reversed Doubly Linked List:");
DoublyLinkedList.reverseDoublyLinkedListBruteForceApproach();
DoublyLinkedList.printDoublyLinkedList();
console.log("Reversing Doubly Linked List again Using Optimised Approach:");
DoublyLinkedList.reverseDoublyLinkedListOptimisedApproach();
DoublyLinkedList.printDoublyLinkedList();
Console Output
Click "Run Code" above to execute and view output...