Given a linked list containing N nodes and a positive integer K where K should be less than or equal to N. The task is to print the last K nodes of the list in reverse order.
Examples:
Input : list: 1->2->3->4->5, K = 2 Output : 5 4 Input : list: 3->10->6->9->12->2->8, K = 4 Output : 8 2 12 9
The solution discussed in previous post uses recursive approach. The following article discusses three iterative approaches to solve the above problem.
Approach 1: The idea is to use stack data structure. Push all the linked list nodes data value to stack and pop first K elements and print them.
Below is the implementation of above approach:
C++
// C++ implementation to print the last k nodes// of linked list in reverse order#include <bits/stdc++.h>using namespace std;// Structure of a nodestruct Node { int data; Node* next;};// Function to get a new nodeNode* getNode(int data){ // allocate space Node* newNode = new Node; // put in data newNode->data = data; newNode->next = NULL; return newNode;}// Function to print the last k nodes// of linked list in reverse ordervoid printLastKRev(Node* head, int k){ // if list is empty if (!head) return; // Stack to store data value of nodes. stack<int> st; // Push data value of nodes to stack while (head) { st.push(head->data); head = head->next; } int cnt = 0; // Pop first k elements of stack and // print them. while (cnt < k) { cout << st.top() << " "; st.pop(); cnt++; }}// Driver codeint main(){ // Create list: 1->2->3->4->5 Node* head = getNode(1); head->next = getNode(2); head->next->next = getNode(3); head->next->next->next = getNode(4); head->next->next->next->next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k); return 0;} |
Java
// Java implementation to print the last k nodes// of linked list in reverse orderimport java.util.*;class GFG {// Structure of a nodestatic class Node{ int data; Node next;};// Function to get a new nodestatic Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;}// Function to print the last k nodes// of linked list in reverse orderstatic void printLastKRev(Node head, int k){ // if list is empty if (head == null) return; // Stack to store data value of nodes. Stack<Integer> st = new Stack<Integer>(); // Push data value of nodes to stack while (head != null) { st.push(head.data); head = head.next; } int cnt = 0; // Pop first k elements of stack and // print them. while (cnt < k) { System.out.print(st.peek() + " "); st.pop(); cnt++; }}// Driver codepublic static void main(String[] args){ // Create list: 1->2->3->4->5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation to print the last k nodes # of linked list in reverse orderimport sysimport math# Structure of a node class Node: def __init__(self,data): self.data = data self.next = None # Function to get a new nodedef getNode(data): # allocate space and return new node return Node(data)# Function to print the last k nodes # of linked list in reverse order def printLastKRev(head,k): # if list is empty if not head: return # Stack to store data value of nodes. stack = [] # Push data value of nodes to stack while(head): stack.append(head.data) head = head.next cnt = 0 # Pop first k elements of stack and # print them. while(cnt < k): print("{} ".format(stack[-1]),end="") stack.pop() cnt += 1 # Driver code if __name__=='__main__': # Create list: 1->2->3->4->5 head = getNode(1) head.next = getNode(2) head.next.next = getNode(3) head.next.next.next = getNode(4) head.next.next.next.next = getNode(5) k = 4 # print the last k nodes printLastKRev(head,k)# This Code is Contributed by Vikash Kumar 37 |
C#
// C# implementation to print the last k nodes// of linked list in reverse orderusing System;using System.Collections.Generic;class GFG {// Structure of a nodepublic class Node{ public int data; public Node next;};// Function to get a new nodestatic Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;}// Function to print the last k nodes// of linked list in reverse orderstatic void printLastKRev(Node head, int k){ // if list is empty if (head == null) return; // Stack to store data value of nodes. Stack<int> st = new Stack<int>(); // Push data value of nodes to stack while (head != null) { st.Push(head.data); head = head.next; } int cnt = 0; // Pop first k elements of stack and // print them. while (cnt < k) { Console.Write(st.Peek() + " "); st.Pop(); cnt++; }}// Driver codepublic static void Main(String[] args){ // Create list: 1->2->3->4->5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k);}}// This code contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation to print the last k nodes// of linked list in reverse order // Structure of a nodeclass Node { constructor(val) { this.data = val; this.next = null; }} // Function to get a new node function getNode(data) { // allocate space var newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode; } // Function to print the last k nodes // of linked list in reverse order function printLastKRev(head , k) { // if list is empty if (head == null) return; // Stack to store data value of nodes. var st = []; // Push data value of nodes to stack while (head != null) { st.push(head.data); head = head.next; } var cnt = 0; // Pop first k elements of stack and // print them. while (cnt < k) { document.write(st.pop() + " "); cnt++; } } // Driver code // Create list: 1->2->3->4->5 var head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); var k = 4; // print the last k nodes printLastKRev(head, k);// This code contributed by aashish1995</script> |
Output:
5 4 3 2
Time Complexity: O(N)
Auxiliary Space: O(N)
The auxiliary space of the above approach can be reduced to O(k). The idea is to use two pointers. Place first pointer to beginning of the list and move second pointer to k-th node form beginning. Then find k-th node from end using approach discussed in this article: Find kth node from end of linked list. After finding kth node from end push all the remaining nodes in the stack. Pop all elements one by one from stack and print them.
Below is the implementation of the above efficient approach:
C++
// C++ implementation to print the last k nodes// of linked list in reverse order#include <bits/stdc++.h>using namespace std;// Structure of a nodestruct Node { int data; Node* next;};// Function to get a new nodeNode* getNode(int data){ // allocate space Node* newNode = new Node; // put in data newNode->data = data; newNode->next = NULL; return newNode;}// Function to print the last k nodes// of linked list in reverse ordervoid printLastKRev(Node* head, int k){ // if list is empty if (!head) return; // Stack to store data value of nodes. stack<int> st; // Declare two pointers. Node *first = head, *sec = head; int cnt = 0; // Move second pointer to kth node. while (cnt < k) { sec = sec->next; cnt++; } // Move first pointer to kth node from end while (sec) { first = first->next; sec = sec->next; } // Push last k nodes in stack while (first) { st.push(first->data); first = first->next; } // Last k nodes are reversed when pushed // in stack. Pop all k elements of stack // and print them. while (!st.empty()) { cout << st.top() << " "; st.pop(); }}// Driver codeint main(){ // Create list: 1->2->3->4->5 Node* head = getNode(1); head->next = getNode(2); head->next->next = getNode(3); head->next->next->next = getNode(4); head->next->next->next->next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k); return 0;} |
Java
// Java implementation to print // the last k nodes of linked list// in reverse orderimport java.util.*;class GFG{// Structure of a nodestatic class Node { int data; Node next;};// Function to get a new nodestatic Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;}// Function to print the last k nodes// of linked list in reverse orderstatic void printLastKRev(Node head, int k){ // if list is empty if (head == null) return; // Stack to store data value of nodes. Stack<Integer> st = new Stack<Integer>(); // Declare two pointers. Node first = head, sec = head; int cnt = 0; // Move second pointer to kth node. while (cnt < k) { sec = sec.next; cnt++; } // Move first pointer to kth node from end while (sec != null) { first = first.next; sec = sec.next; } // Push last k nodes in stack while (first != null) { st.push(first.data); first = first.next; } // Last k nodes are reversed when pushed // in stack. Pop all k elements of stack // and print them. while (!st.empty()) { System.out.print(st.peek() + " "); st.pop(); }}// Driver codepublic static void main(String[] args){ // Create list: 1->2->3->4->5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k);}}// This code is contributed by Princi Singh |
Python3
# Python3 implementation to print the last k nodes# of linked list in reverse order# Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None# Function to get a new nodedef getNode(data): # allocate space newNode = Node(0) # put in data newNode.data = data newNode.next = None return newNode# Function to print the last k nodes# of linked list in reverse orderdef printLastKRev( head, k): # if list is empty if (head == None): return # Stack to store data value of nodes. st = [] # Declare two pointers. first = head sec = head cnt = 0 # Move second pointer to kth node. while (cnt < k) : sec = sec.next cnt = cnt + 1 # Move first pointer to kth node from end while (sec != None): first = first.next sec = sec.next # Push last k nodes in stack while (first != None): st.append(first.data) first = first.next # Last k nodes are reversed when pushed # in stack. Pop all k elements of stack # and print them. while (len(st)): print( st[-1], end= " ") st.pop()# Driver code# Create list: 1.2.3.4.5head = getNode(1)head.next = getNode(2)head.next.next = getNode(3)head.next.next.next = getNode(4)head.next.next.next.next = getNode(5)k = 4# print the last k nodesprintLastKRev(head, k)# This code is contributed by Arnab Kundu |
C#
// C# implementation to print // the last k nodes of linked list// in reverse orderusing System;using System.Collections.Generic; class GFG{// Structure of a nodeclass Node { public int data; public Node next;};// Function to get a new nodestatic Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;}// Function to print the last k nodes// of linked list in reverse orderstatic void printLastKRev(Node head, int k){ // if list is empty if (head == null) return; // Stack to store data value of nodes. Stack<int> st = new Stack<int>(); // Declare two pointers. Node first = head, sec = head; int cnt = 0; // Move second pointer to kth node. while (cnt < k) { sec = sec.next; cnt++; } // Move first pointer to kth node from end while (sec != null) { first = first.next; sec = sec.next; } // Push last k nodes in stack while (first != null) { st.Push(first.data); first = first.next; } // Last k nodes are reversed when pushed // in stack. Pop all k elements of stack // and print them. while (st.Count != 0) { Console.Write(st.Peek() + " "); st.Pop(); }}// Driver codepublic static void Main(String[] args){ // Create list: 1->2->3->4->5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k);}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation to print // the last k nodes of linked list // in reverse order // Structure of a node class Node { constructor() { this.data = 0; this.next = null; } } // Function to get a new node function getNode(data) { // allocate space var newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode; } // Function to print the last k nodes // of linked list in reverse order function printLastKRev(head, k) { // if list is empty if (head == null) return; // Stack to store data value of nodes. var st = []; // Declare two pointers. var first = head, sec = head; var cnt = 0; // Move second pointer to kth node. while (cnt < k) { sec = sec.next; cnt++; } // Move first pointer to kth node from end while (sec != null) { first = first.next; sec = sec.next; } // Push last k nodes in stack while (first != null) { st.push(first.data); first = first.next; } // Last k nodes are reversed when pushed // in stack. Pop all k elements of stack // and print them. while (st.length != 0) { document.write(st[st.length - 1] + " "); st.pop(); } } // Driver code // Create list: 1->2->3->4->5 var head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); var k = 4; // print the last k nodes printLastKRev(head, k); </script> |
Output:
5 4 3 2
Time Complexity: O(N)
Auxiliary Space: O(k)
Approach-2:
- Count the number of nodes in the linked list.
- Declare an array with the number of nodes as its size.
- Start storing the value of nodes of the linked list from the end of the array i.e. reverse manner.
- Print k values from starting of the array.
C++
#include <iostream> using namespace std; // Structure of a node struct Node { int data; Node* next; }; // Function to get a new node Node* getNode(int data){ // allocate space Node* newNode = new Node; // put in data newNode->data = data; newNode->next = NULL; return newNode; } // Function to print the last k nodes // of linked list in reverse order void printLastKRev(Node* head, int& count, int k) { struct Node* cur = head; while(cur != NULL){ count++; cur = cur->next; } int arr[count], temp = count; cur = head; while(cur != NULL){ arr[--temp] = cur->data; cur = cur->next; } for(int i = 0; i < k; i++) cout << arr[i] << " ";} //// Driver code int main() { // Create list: 1->2->3->4->5 Node* head = getNode(1); head->next = getNode(2); head->next->next = getNode(3); head->next->next->next = getNode(4); head->next->next->next->next = getNode(5); head->next->next->next->next->next = getNode(10); int k = 4, count = 0; // print the last k nodes printLastKRev(head, count, k); return 0; } |
Java
// Java code implementation for above approachclass GFG { // Structure of a node static class Node{ int data; Node next; }; // Function to get a new node static Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode; } // Function to print the last k nodes // of linked list in reverse order static void printLastKRev(Node head, int count, int k) { Node cur = head; while(cur != null) { count++; cur = cur.next; } int []arr = new int[count]; int temp = count; cur = head; while(cur != null) { arr[--temp] = cur.data; cur = cur.next; } for(int i = 0; i < k; i++) System.out.print(arr[i] + " ");} // Driver code public static void main(String[] args) { // Create list: 1.2.3.4.5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); head.next.next.next.next.next = getNode(10); int k = 4, count = 0; // print the last k nodes printLastKRev(head, count, k); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 code implementation for above approach# Structure of a node class Node: def __init__(self, data): self.data = data self.next = None # Function to get a new node def getNode(data): # allocate space newNode = Node(data) return newNode # Function to print the last k nodes # of linked list in reverse order def printLastKRev(head, count,k): cur = head; while(cur != None): count += 1 cur = cur.next; arr = [0 for i in range(count)] temp = count; cur = head; while(cur != None): temp -= 1 arr[temp] = cur.data; cur = cur.next; for i in range(k): print(arr[i], end = ' ') # Driver code if __name__=='__main__': # Create list: 1.2.3.4.5 head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); head.next.next.next.next.next = getNode(10); k = 4 count = 0; # print the last k nodes printLastKRev(head, count, k); # This code is contributed by rutvik_56 |
C#
// C# code implementation for above approachusing System;class GFG { // Structure of a node class Node{ public int data; public Node next; }; // Function to get a new node static Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode; } // Function to print the last k nodes // of linked list in reverse order static void printLastKRev(Node head, int count, int k) { Node cur = head; while(cur != null) { count++; cur = cur.next; } int []arr = new int[count]; int temp = count; cur = head; while(cur != null) { arr[--temp] = cur.data; cur = cur.next; } for(int i = 0; i < k; i++) Console.Write(arr[i] + " ");} // Driver code public static void Main(String[] args) { // Create list: 1.2.3.4.5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); head.next.next.next.next.next = getNode(10); int k = 4, count = 0; // print the last k nodes printLastKRev(head, count, k); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation of the approach// Structure of a nodeclass Node { constructor() { this.data = 0; this.next = null; } }// Function to get a new nodefunction getNode( data){ // allocate space var newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;} // Function to print the last k nodes// of linked list in reverse orderfunction printLastKRev( head, count, k){ var cur = head; while(cur != null) { count++; cur = cur.next; } let arr = new Array(count); let temp = count; cur = head; while(cur != null) { arr[--temp] = cur.data; cur = cur.next; } for(let i = 0; i < k; i++) document.write(arr[i] + " ");}// Driver Code// Create list: 1.2.3.4.5var head = getNode(1);head.next = getNode(2);head.next.next = getNode(3);head.next.next.next = getNode(4);head.next.next.next.next = getNode(5);head.next.next.next.next.next = getNode(10); let k = 4, count = 0; // print the last k nodesprintLastKRev(head, count, k);// This code is contributed b jana_sayantan</script> |
Output:
10 5 4 3
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach-3: The idea is to first reverse the linked list iteratively as discussed in following post: Reverse a linked list. After reversing print first k nodes of the reversed list. After printing restore the list by reversing the list again.
Below is the implementation of above approach:
C++
// C++ implementation to print the last k nodes// of linked list in reverse order#include <bits/stdc++.h>using namespace std;// Structure of a nodestruct Node { int data; Node* next;};// Function to get a new nodeNode* getNode(int data){ // allocate space Node* newNode = new Node; // put in data newNode->data = data; newNode->next = NULL; return newNode;}// Function to reverse the linked list.Node* reverseLL(Node* head){ if (!head || !head->next) return head; Node *prev = NULL, *next = NULL, *curr = head; while (curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev;}// Function to print the last k nodes// of linked list in reverse ordervoid printLastKRev(Node* head, int k){ // if list is empty if (!head) return; // Reverse linked list. head = reverseLL(head); Node* curr = head; int cnt = 0; // Print first k nodes of linked list. while (cnt < k) { cout << curr->data << " "; cnt++; curr = curr->next; } // Restore the list. head = reverseLL(head);}// Driver codeint main(){ // Create list: 1->2->3->4->5 Node* head = getNode(1); head->next = getNode(2); head->next->next = getNode(3); head->next->next->next = getNode(4); head->next->next->next->next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k); return 0;} |
Java
// Java implementation to print the last k nodes// of linked list in reverse orderimport java.util.*;class GFG{// Structure of a nodestatic class Node { int data; Node next;};// Function to get a new nodestatic Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;}// Function to reverse the linked list.static Node reverseLL(Node head){ if (head == null || head.next == null) return head; Node prev = null, next = null, curr = head; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev;}// Function to print the last k nodes// of linked list in reverse orderstatic void printLastKRev(Node head, int k){ // if list is empty if (head == null) return; // Reverse linked list. head = reverseLL(head); Node curr = head; int cnt = 0; // Print first k nodes of linked list. while (cnt < k) { System.out.print(curr.data + " "); cnt++; curr = curr.next; } // Restore the list. head = reverseLL(head);}// Driver codepublic static void main(String[] args){ // Create list: 1->2->3->4->5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to print the # last k nodes of linked list in # reverse order# Structure of a nodeclass Node: def __init__(self, data): self.data = data self.next = None # Function to get a new nodedef getNode(data): # Allocate space newNode = Node(data) return newNode# Function to reverse the linked list.def reverseLL(head): if (not head or not head.next): return head prev = None next = None curr = head; while (curr): next = curr.next curr.next = prev prev = curr curr = next return prev # Function to print the last k nodes# of linked list in reverse orderdef printLastKRev(head, k): # If list is empty if (not head): return # Reverse linked list. head = reverseLL(head) curr = head cnt = 0 # Print first k nodes of linked list. while (cnt < k): print(curr.data, end = ' ') cnt += 1 curr = curr.next # Restore the list. head = reverseLL(head)# Driver codeif __name__=='__main__': # Create list: 1.2.3.4.5 head = getNode(1) head.next = getNode(2) head.next.next = getNode(3) head.next.next.next = getNode(4) head.next.next.next.next = getNode(5) k = 4 # Print the last k nodes printLastKRev(head, k)# This code is contributed by pratham76 |
C#
// C# implementation to print the last k nodes// of linked list in reverse orderusing System;class GFG{// Structure of a nodepublic class Node { public int data; public Node next;};// Function to get a new nodestatic Node getNode(int data){ // allocate space Node newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;}// Function to reverse the linked list.static Node reverseLL(Node head){ if (head == null || head.next == null) return head; Node prev = null, next = null, curr = head; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev;}// Function to print the last k nodes// of linked list in reverse orderstatic void printLastKRev(Node head, int k){ // if list is empty if (head == null) return; // Reverse linked list. head = reverseLL(head); Node curr = head; int cnt = 0; // Print first k nodes of linked list. while (cnt < k) { Console.Write(curr.data + " "); cnt++; curr = curr.next; } // Restore the list. head = reverseLL(head);}// Driver codepublic static void Main(String[] args){ // Create list: 1->2->3->4->5 Node head = getNode(1); head.next = getNode(2); head.next.next = getNode(3); head.next.next.next = getNode(4); head.next.next.next.next = getNode(5); int k = 4; // print the last k nodes printLastKRev(head, k);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation to print the last k nodes// of linked list in reverse order// Structure of a nodeclass Node{ constructor() { this.data = 0; this.next = null; }}// Function to get a new nodefunction getNode(data){ // allocate space let newNode = new Node(); // put in data newNode.data = data; newNode.next = null; return newNode;}// Function to reverse the linked list.function reverseLL(head){ if (head == null || head.next == null) return head; let prev = null, next = null, curr = head; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev;}// Function to print the last k nodes// of linked list in reverse orderfunction printLastKRev(head,k){ // if list is empty if (head == null) return; // Reverse linked list. head = reverseLL(head); let curr = head; let cnt = 0; // Print first k nodes of linked list. while (cnt < k) { document.write(curr.data + " "); cnt++; curr = curr.next; } // Restore the list. head = reverseLL(head);}// Driver code// Create list: 1->2->3->4->5let head = getNode(1);head.next = getNode(2);head.next.next = getNode(3);head.next.next.next = getNode(4);head.next.next.next.next = getNode(5);let k = 4;// print the last k nodesprintLastKRev(head, k);// This code is contributed by avanitrachhadiya2155</script> |
Output:
5 4 3 2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
