Print the last k nodes of the linked list in reverse.

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 than k.
  • 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).