How to useRecursion in Javascript
Algorithm:
getnth(node,n)
1. Initialize count = 0
2. if count==n
return node->data
3. else
return getnth(node->next, n-1)
Implementation:
Javascript
// JavaScript program to find n'th node // of a linked list using recursion // Linked List node class Node { constructor(val) { this.data = val; this.next = null; } } /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */function push(head, new_data) { // Allocate node let new_node = new Node(new_data); // Put in the data new_node.data = new_data; new_node.next = head; head = new_node; return head; } /* Takes head pointer of the linked list and index as arguments and return data at index */function GetNth(head, n) { let count = 0; // Edge case - if head is null if (head == null) return -1; // if count equal too n return node.data if (count == n) return head.data; // Recursively decrease n and increase // head to next pointer return GetNth(head.next, n - 1); } // Driver code // Start with the empty list let head = null; // Use push() to construct list // 1 -> 12 -> 1 -> 4 -> 1 head = push(head, 1); head = push(head, 4); head = push(head, 1); head = push(head, 12); head = push(head, 1); // Check the count function console.log("Element at index 3 is ", GetNth(head, 3)); |
Output
Element at index 3 is 4
Time Complexity: O(n)
Space Complexity: O(n) for call stack because using recursion
Please refer complete article on Write a function to get Nth node in a Linked List for more details!
Javascript Program For Writing A Function To Get Nth Node In A Linked List
Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position.
Example:
Input: 1 -> 10 -> 30 -> 14, index = 2
Output: 30
Explanation: The node at index 2 is 30