Enfoque recursivo para encontrar el Node n desde el final en la lista enlazada

Encuentre el Node n desde el final en la lista enlazada dada usando un enfoque recursivo.

Ejemplos: 

Input : list: 4->2->1->5->3
         n = 2
Output : 5

Algoritmo:  

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"

Nota: Los parámetros count y nth_last serán variables de puntero en findNthFromLast() . 

// 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 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 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# 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

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

Producción:  

Nth node from last is: 5

Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces, donde N es el número de Nodes en la lista vinculada.

Espacio auxiliar : O (N) para la pila de llamadas desde que se usa la recursividad