Recursive Approach to find nth node from the end in the linked list

0 0 6 minutes read

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

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 zambiatek!