Find the nth node from the end in the given linked list using a recursive approach.
Examples:
Input : list: 4->2->1->5->3
n = 2
Output : 5
Algorithm:
findNthFromLast(head, n, count, nth_last)
if head == NULL then
return
findNthFromLast(head->next, n, count, nth_last)
count = count + 1
if count == n then
nth_last = head
findNthFromLastUtil(head, n)
Initialize nth_last = NULL
Initialize count = 0
findNthFromLast(head, n, &count, &nth_last)
if nth_last != NULL then
print nth_last->data
else
print "Node does not exists"
Note: Parameters count and nth_last will be pointer variables in findNthFromLast().
C++
// C++ implementation to recursively find the nth node from// the last of the linked list#include <bits/stdc++.h>using namespace std;// structure of a node of a linked liststruct 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 recursively find the nth node from// the last of the linked listvoid findNthFromLast(Node* head, int n, int* count, Node** nth_last){ // if list is empty if (!head) return; // recursive call findNthFromLast(head->next, n, count, nth_last); // increment count *count = *count + 1; // if true, then head is the nth node from the last if (*count == n) *nth_last = head;}// utility function to find the nth node from// the last of the linked listvoid findNthFromLastUtil(Node* head, int n){ // Initialize Node* nth_last = NULL; int count = 0; // find nth node from the last findNthFromLast(head, n, &count, &nth_last); // if node exists, then print it if (nth_last != NULL) cout << "Nth node from last is: " << nth_last->data; else cout << "Node does not exists";}// Driver program to test aboveint main(){ // linked list: 4->2->1->5->3 Node* head = getNode(4); head->next = getNode(2); head->next->next = getNode(1); head->next->next->next = getNode(5); head->next->next->next->next = getNode(3); int n = 2; findNthFromLastUtil(head, n); return 0;} |
Java
// Java implementation to recursively // find the nth node from the last// of the linked list import java.util.*;class GFG{static int count = 0, data = 0;// a node of a linked list 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 recursively // find the nth node from // the last of the linked list static void findNthFromLast(Node head, int n, Node nth_last) { // if list is empty if (head == null) return; // recursive call findNthFromLast(head.next, n, nth_last); // increment count count = count + 1; // if true, then head is the // nth node from the last if (count == n) { data = head.data; }} // utility function to find // the nth node from the last// of the linked list static void findNthFromLastUtil(Node head, int n) { // Initialize Node nth_last = new Node(); // find nth node from the last findNthFromLast(head, n, nth_last); // if node exists, then print it if (nth_last != null) System.out.println("Nth node from last is: " + data); else System.out.println("Node does not exists"); } // Driver Codepublic static void main(String args[]){ // linked list: 4.2.1.5.3 Node head = getNode(4); head.next = getNode(2); head.next.next = getNode(1); head.next.next.next = getNode(5); head.next.next.next.next = getNode(3); int n = 2; findNthFromLastUtil(head, n); } }// This code is contributed // by Arnab Kundu |
Python
# Python implementation to recursively # find the nth node from the last # of the linked list count = 0data = 0# a node of a linked list class Node(object): def __init__(self, d): self.data = d self.next = None# function to get a new node def getNode(data): # allocate space newNode = Node(0) # put in data newNode.data = data newNode.next = None return newNode # function to recursively # find the nth node from # the last of the linked list def findNthFromLast(head, n, nth_last) : global count global data # if list is empty if (head == None): return # recursive call findNthFromLast(head.next, n, nth_last) # increment count count = count + 1 # if true, then head is the # nth node from the last if (count == n) : data = head.data # utility function to find # the nth node from the last # of the linked list def findNthFromLastUtil(head, n) : global count global data # Initialize nth_last = Node(0) count = 0 # find nth node from the last findNthFromLast(head, n, nth_last) # if node exists, then print it if (nth_last != None) : print("Nth node from last is: " , data) else: print("Node does not exists") # Driver Code # linked list: 4.2.1.5.3 head = getNode(4) head.next = getNode(2) head.next.next = getNode(1) head.next.next.next = getNode(5) head.next.next.next.next = getNode(3) n = 2findNthFromLastUtil(head, n) # This code is contributed # by Arnab Kundu |
C#
// C# implementation to recursively // find the nth node from the last// of the linked list using System;public class GFG{ static int count = 0, data = 0; // a node of a linked list 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 recursively // find the nth node from // the last of the linked list static void findNthFromLast(Node head, int n, Node nth_last) { // if list is empty if (head == null) return; // recursive call findNthFromLast(head.next, n, nth_last); // increment count count = count + 1; // if true, then head is the // nth node from the last if (count == n) { data = head.data; }} // utility function to find // the nth node from the last// of the linked list static void findNthFromLastUtil(Node head, int n) { // Initialize Node nth_last = new Node(); count = 0; // find nth node from the last findNthFromLast(head, n, nth_last); // if node exists, then print it if (nth_last != null) Console.WriteLine("Nth node from last is: " + data); else Console.WriteLine("Node does not exists"); } // Driver Codepublic static void Main(String []args){ // linked list: 4.2.1.5.3 Node head = getNode(4); head.next = getNode(2); head.next.next = getNode(1); head.next.next.next = getNode(5); head.next.next.next.next = getNode(3); int n = 2; findNthFromLastUtil(head, n); } }// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to recursively // find the nth node from the last // of the linked list var count = 0, data = 0; // a node of a linked list 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 recursively // find the nth node from // the last of the linked list function findNthFromLast(head, n, nth_last) { // if list is empty if (head == null) return; // recursive call findNthFromLast(head.next, n, nth_last); // increment count count = count + 1; // if true, then head is the // nth node from the last if (count == n) { data = head.data; } } // utility function to find // the nth node from the last // of the linked list function findNthFromLastUtil(head, n) { // Initialize var nth_last = new Node(); count = 0; // find nth node from the last findNthFromLast(head, n, nth_last); // if node exists, then print it if (nth_last != null) document.write("Nth node from last is: " + data + "<br>"); else document.write("Node does not exists <br>"); } // Driver Code // linked list: 4.2.1.5.3 var head = getNode(4); head.next = getNode(2); head.next.next = getNode(1); head.next.next.next = getNode(5); head.next.next.next.next = getNode(3); var n = 2; findNthFromLastUtil(head, n); </script> |
Output:
Nth node from last is: 5
Time Complexity: O(N), as we are using a loop to traverse N times, where N is the number of Nodes in the linked list.
Auxiliary Space: O(N) for call stack since using recursion
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!
