Recursive Approach to find nth node from the end in the linked list
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 list 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 recursively find the nth node from // the last of the linked list void 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 list void 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 above int 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 Code public 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 = 0 data = 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 = 2 findNthFromLastUtil(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 Code public 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