Horje
JavaScript Program to Reverse a Linked List

A linked list is a data structure where elements are stored in nodes, and each node points to the next node in the sequence. Reversing a linked list involves changing the direction of the pointers, making the last node the new head and the head the new tail.

Below are the approaches to reverse a linked list in JavaScript:

Table of Content

Reversing a Linked List Using Iteration

We will use a loop to iterate through the elements and the pointer nodes of the linked list and change the next pointers of each node in such a way that their order is reversed.

Example: The below code iteratively reverses the linked list in JavaScript.

Javascript

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}
 
class LinkedList {
    constructor() {
        this.head = null;
    }
 
    insertFirst(data) {
        this.head = new Node(data, this.head);
    }
 
    printList() {
        let current = this.head;
        while (current !== null) {
            console.log(current.data);
            current = current.next;
        }
    }
    reverse() {
        let prev = null;
        let current = this.head;
        let next = null;
 
        while (current !== null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        this.head = prev;
    }
}
 
const linkedList = new LinkedList();
 
linkedList.insertFirst(3);
linkedList.insertFirst(2);
linkedList.insertFirst(1);
 
console.log("Original Linked List:");
linkedList.printList();
 
linkedList.reverse();
 
console.log("\nReversed Linked List:");
linkedList.printList();

Output

Original Linked List:
1
2
3

Reversed Linked List:
3
2
1

Time Complexity: O(N)

Space Complexity: O(1)

Reversing a Linked List Using Recursion

Recursion is a process in which a function calls itself directly or indirectly. We are going to reverse the linked list by iterating through its elements using recursion and change their node values.

Example: The below code is the implementation of the recursive approach to reverse the linked list in JavaScript.

Javascript

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}
 
class LinkedList {
    constructor() {
        this.head = null;
    }
 
    insertFirst(data) {
        this.head = new Node(data, this.head);
    }
 
    reverseRecursiveUtil(current, prev) {
        if (current === null) {
            this.head = prev;
            return;
        }
 
        const next = current.next;
        current.next = prev;
 
        this.reverseRecursiveUtil(next, current);
    }
 
    reverseRecursive() {
        this.reverseRecursiveUtil(this.head, null);
    }
 
    printList() {
        let current = this.head;
        while (current !== null) {
            console.log(current.data);
            current = current.next;
        }
    }
}
 
const linkedList = new LinkedList();
 
linkedList.insertFirst(3);
linkedList.insertFirst(2);
linkedList.insertFirst(1);
 
console.log("Original Linked List:");
linkedList.printList();
 
linkedList.reverseRecursive();
 
console.log("\nReversed Linked List:");
linkedList.printList();

Output

Original Linked List:
1
2
3

Reversed Linked List:
3
2
1

Time Complexity: O(N)

Space Complexity: O(N)


 


Reffered: https://www.geeksforgeeks.org

JavaScript

Related
JavaScript Program to Find the Smallest Among Three Numbers JavaScript Program to Find the Smallest Among Three Numbers
How to Iterate Array of Objects in TypeScript ? How to Iterate Array of Objects in TypeScript ?
How to Remove Keys from a TypeScript Dictionary ? How to Remove Keys from a TypeScript Dictionary ?
JavaScript Program to Get a Non-Repeating Character From the Given String JavaScript Program to Get a Non-Repeating Character From the Given String
How to Convert String to Boolean in TypeScript ? How to Convert String to Boolean in TypeScript ?

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje