Programa Java para imprimir el Node N desde el final de una lista vinculada (duplicado)

Dada una lista enlazada y un número n, escriba una función que devuelva el valor en el Node n desde el final de la lista enlazada.
Por ejemplo, si la entrada está debajo de la lista y n = 3, entonces la salida es «B»

Método 1 (Usar la longitud de la lista enlazada) 
1) Calcular la longitud de la Lista enlazada. Sea la longitud len. 
2) Imprima el (len – n + 1) Node desde el principio de la lista enlazada. 
Concepto de puntero doble: el primer puntero se usa para almacenar la dirección de la variable y el segundo puntero se usa para almacenar la dirección del primer puntero. Si deseamos cambiar el valor de una variable por una función, le pasamos un puntero. Y si deseamos cambiar el valor de un puntero (es decir, debería empezar a apuntar a otra cosa), pasamos puntero a puntero.
  

A continuación se muestra la implementación del enfoque anterior:

35

A continuación se muestra un código C recursivo para el mismo método. Gracias a Anuj Bansal por proporcionar el siguiente código. 

static void printNthFromLast(Node head, int n)
{
    static int i = 0;
 
    if (head == null)
        return;
    printNthFromLast(head.next, n);
 
    if (++i == n)
        System.out.print(head.data);
}
 
// This code is contributed by rutvik_56.

Complejidad de tiempo: O(n) donde n es la longitud de la lista enlazada. 
Método 2 (Usar dos punteros) 
Mantener dos punteros: puntero de referencia y puntero principal. Inicialice tanto los punteros de referencia como los principales en head. Primero, mueva el puntero de referencia a n Nodes desde la cabeza. Ahora mueva ambos punteros uno por uno hasta que el puntero de referencia llegue al final. Ahora el puntero principal apuntará al Node n desde el final. Devuelve el puntero principal.
La imagen de abajo es una ejecución en seco del enfoque anterior:
 

A continuación se muestra la implementación del enfoque anterior: 
 

Node no. 4 from last is 35 

Complejidad de tiempo: O(n) donde n es la longitud de la lista enlazada. 

Complejidad espacial : O(1) ya que usa espacio constante

Consulte el artículo completo sobre Programa para el Node n desde el final de una lista vinculada para obtener más detalles.