1. Información general
En este tutorial, explicaremos cómo encontrar el elemento intermedio de una lista vinculada en Java.
Presentaremos los problemas principales en las siguientes secciones y mostraremos diferentes enfoques para resolverlos.
2. Seguimiento del tamaño
Este problema se puede resolver fácilmente con solo hacer un seguimiento del tamaño cuando agregamos nuevos elementos a la lista . Si conocemos el tamaño, también sabemos dónde está el elemento del medio, por lo que la solución es trivial.
Veamos un ejemplo usando la implementación de Java de una LinkedList :
public static Optional findMiddleElementLinkedList( LinkedList linkedList) { if (linkedList == null || linkedList.isEmpty()) { return Optional.empty(); } return Optional.of(linkedList.get( (linkedList.size() - 1) / 2)); }Si revisamos el código interno de la clase LinkedList , podemos ver que en este ejemplo solo estamos recorriendo la lista hasta llegar al elemento del medio:
Node node(int index) { if (index > 1)) { Node x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } }3. Encontrar el medio sin conocer el tamaño
Es muy común que encontremos problemas en los que solo tenemos el nodo principal de una lista vinculada y necesitamos encontrar el elemento intermedio. En este caso, no conocemos el tamaño de la lista, lo que hace que este problema sea más difícil de resolver.
En las siguientes secciones mostraremos varios enfoques para resolver este problema, pero primero, necesitamos crear una clase para representar un nodo de la lista.
Creemos una clase de nodo , que almacena valores de cadena :
public static class Node { private Node next; private String data; // constructors/getters/setters public boolean hasNext() { return next != null; } public void setNext(Node next) { this.next = next; } public String toString() { return this.data; } }Además, usaremos este método auxiliar en nuestros casos de prueba para crear una lista enlazada individualmente usando solo nuestros nodos:
private static Node createNodesList(int n) { Node head = new Node("1"); Node current = head; for (int i = 2; i <= n; i++) { Node newNode = new Node(String.valueOf(i)); current.setNext(newNode); current = newNode; } return head; }3.1. Encontrar el tamaño primero
El enfoque más simple para abordar este problema es encontrar primero el tamaño de la lista y luego seguir el mismo enfoque que usamos antes: iterar hasta el elemento del medio.
Veamos esta solución en acción:
public static Optional findMiddleElementFromHead(Node head) { if (head == null) { return Optional.empty(); } // calculate the size of the list Node current = head; int size = 1; while (current.hasNext()) { current = current.next(); size++; } // iterate till the middle element current = head; for (int i = 0; i < (size - 1) / 2; i++) { current = current.next(); } return Optional.of(current.data()); }Como podemos ver, este código recorre la lista dos veces. Por lo tanto, esta solución tiene un rendimiento deficiente y no se recomienda .
3.2. Encontrar el elemento medio en una sola pasada de forma iterativa
Ahora vamos a mejorar la solución anterior encontrando el elemento del medio con solo una iteración sobre la lista.
Para hacerlo de forma iterativa, necesitamos dos punteros para recorrer la lista al mismo tiempo. Un puntero avanzará 2 nodos en cada iteración, y el otro puntero avanzará solo un nodo por iteración .
Cuando el puntero más rápido llega al final de la lista, el puntero más lento estará en el medio:
public static Optional findMiddleElementFromHead1PassIteratively(Node head) { if (head == null) { return Optional.empty(); } Node slowPointer = head; Node fastPointer = head; while (fastPointer.hasNext() && fastPointer.next().hasNext()) { fastPointer = fastPointer.next().next(); slowPointer = slowPointer.next(); } return Optional.ofNullable(slowPointer.data()); }Podemos probar esta solución con una prueba unitaria simple usando listas con números pares e impares de elementos:
@Test public void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( reateNodesList(4)).get()); }3.3. Encontrar el elemento medio en una sola pasada de forma recursiva
Otra forma de resolver este problema de una pasada es mediante la recursividad. Podemos iterar hasta el final de la lista para conocer el tamaño y, en las devoluciones de llamada, solo contamos hasta la mitad del tamaño.
Para hacer esto en Java, vamos a crear una clase auxiliar para mantener las referencias del tamaño de la lista y el elemento medio durante la ejecución de todas las llamadas recursivas:
private static class MiddleAuxRecursion { Node middle; int length = 0; }Ahora, implementemos el método recursivo:
private static void findMiddleRecursively( Node node, MiddleAuxRecursion middleAux) { if (node == null) { // reached the end middleAux.length = middleAux.length / 2; return; } middleAux.length++; findMiddleRecursively(node.next(), middleAux); if (middleAux.length == 0) { // found the middle middleAux.middle = node; } middleAux.length--; }Y finalmente, creemos un método que llame al recursivo:
public static Optional findMiddleElementFromHead1PassRecursively(Node head) { if (head == null) { return Optional.empty(); } MiddleAuxRecursion middleAux = new MiddleAuxRecursion(); findMiddleRecursively(head, middleAux); return Optional.of(middleAux.middle.data()); }Nuevamente, podemos probarlo de la misma manera que lo hicimos antes:
@Test public void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(4)).get()); }4. Conclusión
En este artículo, presentamos el problema de encontrar el elemento intermedio de una lista vinculada en Java y mostramos diferentes formas de resolverlo.
Comenzamos con el enfoque más simple en el que realizamos un seguimiento del tamaño y, después de eso, continuamos con las soluciones para encontrar el elemento intermedio del nodo principal de la lista.
Como siempre, el código fuente completo de los ejemplos está disponible en GitHub.