Listas Enlazadas

Una lista enlazada es una cadena de nodos donde cada nodo tiene un valor y un puntero al siguiente nodo. A diferencia de los arrays (memoria contigua), los nodos pueden estar en cualquier parte de la memoria.

Esto hace la inserción y eliminación al inicio O(1) (solo cambias punteros) mientras que en un array es O(n) porque debes mover todos los demás elementos. La desventaja: no hay acceso por índice; para llegar al elemento 500 debes recorrer 500 nodos.

En entrevistas, los problemas de linked lists se resuelven con patrones específicos. Fast & Slow Pointers (tortuga y liebre): dos punteros a diferentes velocidades detectan ciclos en la lista en O(1) de espacio. Reverse in-place: invertir una lista sin memoria adicional cambiando los punteros iterativamente. Merge two sorted lists: combinar dos listas ordenadas usando el patrón de comparar las cabezas. Estos patrones aparecen repetidamente en entrevistas de empresas top.

// Nodo de lista enlazada
class Nodo {
  constructor(valor) {
    this.valor = valor;
    this.siguiente = null;
  }
}

// Lista Enlazada Simple
class ListaEnlazada {
  constructor() {
    this.cabeza = null;
    this.longitud = 0;
  }
  
  agregarAlFinal(valor) {
    const nuevo = new Nodo(valor);
    if (!this.cabeza) {
      this.cabeza = nuevo;
    } else {
      let actual = this.cabeza;
      while (actual.siguiente) actual = actual.siguiente;
      actual.siguiente = nuevo;
    }
    this.longitud++;
  }
  
  agregarAlInicio(valor) {
    const nuevo = new Nodo(valor);
    nuevo.siguiente = this.cabeza;
    this.cabeza = nuevo;
    this.longitud++;
  }
  
  // Invertir lista - problema clásico de entrevistas
  invertir() {
    let prev = null;
    let actual = this.cabeza;
    while (actual) {
      const siguiente = actual.siguiente;
      actual.siguiente = prev;
      prev = actual;
      actual = siguiente;
    }
    this.cabeza = prev;
  }
  
  // Detectar ciclo (algoritmo de Floyd)
  tieneCiclo() {
    let lento = this.cabeza;
    let rapido = this.cabeza;
    while (rapido && rapido.siguiente) {
      lento = lento.siguiente;
      rapido = rapido.siguiente.siguiente;
      if (lento === rapido) return true;
    }
    return false;
  }
  
  toArray() {
    const result = [];
    let actual = this.cabeza;
    while (actual) {
      result.push(actual.valor);
      actual = actual.siguiente;
    }
    return result;
  }
}