An algorithm to print the last k nodes of the single linked list in reverse order in javascript.
Example
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 k = 5; Output 7 6 5 4 3
We are going to see two different approaches to solve this problem.
Method 1: Recursive approach
Implementation
- We are going to use a recursive function with extra global variable
count
to keep track of elements that we need to print. - We will call the same function recursively with the increased
count
and print the element if the count is less thank
. - As recursive function works like a stack, The bottom function will called first, elements will be printed in reverse order.
//Temp variable to keep the track of the count let count = 0; let printInReverse = (head, k) => { //If head is null then return if(head === null){ return; } //Recursively call the function printInReverse(head.next, k); //Increase the count count++; //Print the elements if(count <= k){ console.log(head.element); } }
Input: let ll = new LinkedList(); ll.append(1); ll.append(2); ll.append(3); ll.append(4); ll.append(5); ll.append(6); let head = ll.getHead(); printInReverse(head, 4); Output: 6 5 4 3
Time complexity: O(n).
Space complexity: O(n) (Call stack).
Method 2: Using Stack to print the last k nodes of linked list in reverse order.
Implementation
- We will copy all the elements from the linked list to the stack.
- Then print k elements from the stack.
- As stack stores data in LIFO order. Elements will be printed in reverse order.
let printInReverseUsingStack = (head, k) => { let stack = new Stack(); //Add all the elements of the list to the stack while(head){ stack.push(head.element); head = head.next; } //Print the list in reverse order while(k-- > 0){ //Prevent from undefined elements //Break if stack is empty if(stack.isEmpty()){ break; } //Print the items console.log(stack.pop()); } }
Input: let ll = new LinkedList(); ll.append(1); ll.append(2); ll.append(3); ll.append(4); ll.append(5); ll.append(6); let head = ll.getHead(); printInReverse(head, 4); Output: 6 5 4 3
Time complexity: O(n).
Space complexity: O(n) (Call stack).