Programa Java para imprimir el Node N desde el final de una lista vinculada – Part 1

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»

linkedlist

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:

Java

// Simple Java program to find n'th node from end of linked list
class LinkedList {
    Node head; // head of the list
 
    /* Linked List node */
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    /* Function to get the nth node from the last of a
       linked list */
    void printNthFromLast(int n)
    {
        int len = 0;
        Node temp = head;
 
        // 1) count the number of nodes in Linked List
        while (temp != null) {
            temp = temp.next;
            len++;
        }
 
        // check if value of n is not more than length of
        // the linked list
        if (len < n)
            return;
 
        temp = head;
 
        // 2) get the (len-n+1)th node from the beginning
        for (int i = 1; i < len - n + 1; i++)
            temp = temp.next;
 
        System.out.println(temp.data);
    }
 
    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);
 
        /* 3. Make next of new Node as head */
        new_node.next = head;
 
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
 
    /*Driver program to test above methods */
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
 
        llist.printNthFromLast(4);
    }
} // This code is contributed by Rajat Mishra
Producción

35

Complejidad temporal: O(n).

Espacio auxiliar : O (1) ya que usa espacio constante

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. 

Java

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: 
 

Java

// Java program to find n'th
// node from end using slow and
// fast pointers
class LinkedList
{
    Node head; // head of the list
 
    /* Linked List node */
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    /* Function to get the
      nth node from end of list */
    void printNthFromLast(int n)
    {
        Node main_ptr = head;
        Node ref_ptr = head;
 
        int count = 0;
        if (head != null)
        {
            while (count < n)
            {
                if (ref_ptr == null)
                {
                    System.out.println(n
                     + " is greater than the no "
                       + " of nodes in the list");
                    return;
                }
                ref_ptr = ref_ptr.next;
                count++;
            }
 
            if(ref_ptr == null)
            {
              
              if(head != null)
                System.out.println("Node no. " + n +
                                   " from last is " +
                                      head.data);
            }
            else
            {
                   
              while (ref_ptr != null)
              {
                  main_ptr = main_ptr.next;
                  ref_ptr = ref_ptr.next;
              }
              System.out.println("Node no. " + n +
                                " from last is " +
                                  main_ptr.data);
            }
        }
    }
 
    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);
 
        /* 3. Make next of new Node as head */
        new_node.next = head;
 
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
 
    /*Driver program to test above methods */
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
 
        llist.printNthFromLast(4);
    }
}
// This code is contributed by Rajat Mishra
Producción

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) usando 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.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *