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)
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
- Reversing a Linked List Using Recursion
Contact Us