Búsqueda de nodos de lista vinculados

Una lista enlazada es una estructura de datos lineales formada por nodos. Cada nodo contiene un campo de datos y un puntero al siguiente nodo. En la lista enlazada, a diferencia de las matrices, los elementos no se almacenan en ubicaciones de memoria contiguas sino en diferentes ubicaciones de memoria. Los diferentes elementos de una lista enlazada se enlazan entre sí mediante punteros.

Aprende más de python con estos temas:

Lista enlazada

La lista de enlaces es uno de los temas importantes desde el punto de vista de la entrevista. Casi todas las grandes empresas hacen preguntas relacionadas con la lista de enlaces en las etapas iniciales. Una de las preguntas más frecuentes que hacen las empresas basadas en los mejores productos, incluidas Amazon, Flipkart, Adobe, es «Obtener un nodo multimedia de lista de enlaces».

El enunciado del problema dice: «Dada una lista enlazada y un vértice que apunta al primer nodo de una lista enlazada, encuentre el nodo medio de la lista enlazada».

Ejemplo de una lista enlazada:

Entrada de lista enlazadaResultado
1->2->3->4->5->NULO3
10->20->30->40->NULO30

Tenga en cuenta que para un número par de nodos en la lista enlazada, habrá dos nodos intermedios. En ese caso, necesitamos imprimir el primer elemento del medio. Los diversos enfoques para resolver este problema se analizan en detalle junto con el código en Java.

Recomendado: Resuélvalo en Codestudio antes de pasar a la solución.

Enfoque 1 Para un nodo intermedio de una lista enlazada

El nodo medio de una Lista Vinculada es el elemento en (Número de Nodos/2) ésima posición. Necesitamos encontrar el elemento en esta posición.

Por lo tanto, el problema se reduce a los dos pasos siguientes:

  • Obtener el número de elementos (recuento) en la lista enlazada
  • Imprime el elemento en la posición (recuento/2)

Algoritmo:

Paso 1) Un enfoque obvio sería iterar a través de la Lista enlazada y una contar una variable que contendrá un recuento del número de nodos en la lista enlazada.

In the code below, the getCount() method is used for this.

Paso 2) Ahora vuelva a iterar a través de la Lista hasta la cuenta/2 y devuelva el Nodo en la cuenta/2.

In the code below, findMiddleNode() method is used for this.

Código:

Para simplificar, el programa a continuación usa solo dos métodos para insertar un nuevo nodo en la Lista enlazada

  1. push() -> Para insertar un nodo al principio de la Lista Enlazada.
  2. insertAtLast() -> Para insertar un nodo al final de la lista enlazada.
public class MiddleNode
{
    Node head;
    // Node class
    class Node{
        int key;
        Node next;
        
        Node(int data)
        {
            key = data;
            next = null;
        }
    }
    
    // Method for inserting node to the front
    public void push(int data)
    {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
    }
    
    // Method for inserting a node at the last
    public void insertAtLast(int data)
    {
        Node new_node = new Node(data);
        if(head == null){
            head = new_node;
            return;
        }
        
        
        Node temp = head;
        while(temp.next != null)
        {
            temp = temp.next;
        }
        
        temp.next = new_node;
        return;
}

 // Method to get the count of number of nodes in the List
    public int getCount()
    {
        int count = 0;
        Node temp = head;
        while(temp!= null)
        {
            count++;
            temp = temp.next;
        }
        return count;
    }
    
    // Method to find the middle node of a linked list
    public void findMiddleNode()
    {
        int count = getCount();
        Node temp = head;
        
        // If the number of nodes are even, then there are
        // two middle nodes print the first middle node
        if(count%2 == 0)
        {
            int i = (count/2) - 1;
            while(i != 0)
            {
                temp = temp.next;
                i--;
            }
            
            System.out.println(temp.key);
        }
        
        // If the number of nodes are even
        else{
            int i = (count/2);
            while(i != 0)
            {
                temp = temp.next;
                i--;
            }
            System.out.println(temp.key);
        }
    }
    

   // A utility method to print the Linked List
    public void printList()
    {
        Node temp = head;
        while(temp != null)
        {
            System.out.print(temp.key + " ");
            temp = temp.next;
        }
    }
    public static void main(String []args)
    {
        MiddleNode ll = new MiddleNode();
        // Making a linked list of odd number of nodes
        // 1->2->3->4->5->NULL
        ll.push(1);
        ll.insertAtLast(2);
        ll.insertAtLast(3);
        ll.insertAtLast(4);
        ll.insertAtLast(5);
        System.out.println("Printing the original Linked List");
        ll.printList();
        System.out.println("\nThe middle node of a Linked list is");
        ll.findMiddleNode();

       // Making a linked list of even number of nodes
       // 10->20->30->40->50->60->NULL
        ll = new MiddleNode();
        ll.push(10);
        ll.insertAtLast(20);
        ll.insertAtLast(30);
        ll.insertAtLast(40);
        ll.insertAtLast(50);
        ll.insertAtLast(60);
         System.out.println("Printing the original Linked List");
        ll.printList();
        System.out.println("\nThe middle node of a Linked list is");
        ll.findMiddleNode();
     }
}

La salida del programa anterior es:

Printing the original Linked List
1 2 3 4 5
The middle node of a Linked List is
3
Printing the original Linked List
10 20 30 40 50 60
The middle node of a Linked List is
30

Análisis de Complejidad:

La lista Vinculada se cruza dos veces. Una vez para toda la Lista Vinculada y en segundo lugar a la mitad de la Lista Vinculada. Entonces, la complejidad del tiempo es O(N) + O(N/2), que es igual a O(N), donde N es el número de elementos en la lista enlazada.

Debido a que no se requiere espacio adicional, la complejidad del espacio es O(1).

Enfoque 2 Para la lista enlazada central

En lugar de recorrer dos veces la lista vinculada, el nodo medio de una lista vinculada también se puede encontrar en un solo recorrido mediante un enfoque de dos puntos.

La idea es utilizar dos direcciones, lenta y rápida, respectivamente. Mueva el puntero lento un paso y el puntero rápido dos pasos. Procediendo de esta manera, cuando el puntero rápido llegue al final de la Lista Enlazada, el puntero lento estará en el medio de la Lista Enlazada.

Algoritmo:

Este enfoque es una ligera variación del enfoque tortuga liebre:

  1. Inicialmente, ambas direcciones apuntan al primer nodo de la Lista enlazada. Mueva el puntero lento una posición y el puntero rápido dos posiciones.
  1. El puntero lento ahora apunta al segundo nodo y el puntero rápido apunta al tercer nodo respectivamente.
  1. El puntero lento ahora apunta al tercer nodo y el puntero rápido ahora apunta al quinto nodo.

Podemos ver claramente que si el puntero rápido no puede hacer la transición o fast.next.next == nulo, entonces el nodo medio es un puntero lento.

El enfoque funciona para una lista vinculada con un número impar de nodos, como se muestra a continuación.

  1. Inicialmente, ambas direcciones apuntan al primer nodo de la lista enlazada. Mueva el puntero lento una posición y el puntero rápido dos posiciones.
  1. Ahora el puntero lento apunta al segundo nodo y el puntero rápido apunta al tercer nodo de la lista Vinculada.
  1. Ahora el puntero lento apunta al tercer nodo y el puntero rápido apunta al último nodo como se muestra a continuación.

Está claro a partir de la ilustración anterior que para un número par de nodos en la lista enlazada, el nodo medio se alcanzará tan pronto como el puntero llegue a cero, y para un número impar de nodos en la lista enlazada, el nodo medio será alcanzado cuando el puntero apunta rápidamente al último nodo.

Código:

A continuación se muestra el código para encontrar el medio de la lista vinculada utilizando un enfoque de dos punteros

// Two pointer approach to find the middle node of a linked list

public void findMiddleNode()
 {
        Node slowPtr = head;
        Node fastPtr = head;
        
        while(fastPtr.next != null && fastPtr.next.next != null)
        {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
        }
        
        System.out.println("Middle node of a linked list is : " + slowPtr.key);
    }

Análisis de Complejidad:

La lista se cambia una vez, por lo que la complejidad temporal del método anterior es O(N), donde N es la longitud de la lista enlazada

La complejidad del espacio es O(1) porque no se usa espacio extra.

Enfoque 3 Para lista enlazada

Si tiene la suerte de que su entrevistador le permita usar el framework de recopilación para la clase Lista vinculada, encontrar el centro de la lista vinculada será relativamente simple.

Código:

import java.util.LinkedList;
public class Main{
    public static void main(String[]args)
    {
        LinkedList<Integer> ll = new LinkedList<>();
        ll.add(10);
        ll.add(20);
        ll.add(30);
        ll.addLast(40);
        ll.addLast(100);
        System.out.println("Given Linked list is : " + ll);
        int mid = ll.get(ll.size()/2);

        System.out.println("Middle node of a linked list is:  " + mid);
    }
}

La salida del programa anterior es:

Given Linked list is: [10, 20, 30, 40, 100]
Middle node of a linked list is: 30

Si bien la mayoría de los entrevistadores prefieren solicitar una implementación directa, algunos entrevistadores pueden solicitar el enfoque anterior específicamente para probar el conocimiento de Collection Framework en Java.

Preguntas frecuentes

¿Cómo encuentras el elemento medio de una lista enlazada?

Para encontrar el elemento medio de una lista enlazada, hay dos enfoques posibles:
1. Recorra la lista de elementos una vez y cuente el número de nodos en la lista. Una vez más, repita la lista esta vez solo hasta la ubicación (recuento/2). El elemento en la posición (recuento/2) es el elemento central.
2. Use un enfoque de dos puntos como se discutió anteriormente

¿Cuál es la complejidad temporal de encontrar el elemento intermedio de una lista enlazada?

La complejidad de tiempo de ambos enfoques, como se discutió anteriormente, es O (N) cuando el tamaño de la lista enlazada es N.

¿Puede una lista enlazada contener elementos duplicados?

Sí, una lista vinculada puede contener elementos duplicados.

Aprende más de programación: