Listas enlazadas en C#: dos punteros que avanzan a distinta velocidad

Las partes 1 a 10 son patrones de concurso. De aquí en adelante la serie cubre los de entrevista, y lo primero que hay que decir sobre las listas enlazadas es que casi nunca vas a ver una en un concurso. Codeforces te da un arreglo. Las entrevistas te dan una lista enlazada todo el tiempo.

Lo segundo es un problema de C#. LinkedList<T> existe en la BCL y es doblemente enlazada: expone LinkedListNode<T> con Next y Previous. Esa no es la estructura de la que hablan estos problemas, y usarla elimina la dificultad en vez de resolverla. Cada programa de aquí declara su propio nodo:

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

Eso es un constructor primario, y es el tipo completo. Cada programa de abajo está completo, se ejecutó en .NET 10, y su salida está pegada de la corrida.

Patrón 51 — El medio, en una sola pasada

Lo obvio es recorrer la lista para contarla, y después recorrer la mitad otra vez. Dos pasadas, y necesitas la longitud.

En vez de eso, mueve dos punteros, uno al doble de velocidad. Cuando el rápido llega al final, el lento va a la mitad.

// C# has no singly-linked node type. LinkedList<T> is DOUBLY linked, exposes
// LinkedListNode<T>, and is not what an interview hands you. Declare your own.
static ListNode? Build(params int[] values)
{
    ListNode? head = null;
    for (int i = values.Length - 1; i >= 0; i--) head = new ListNode(values[i], head);
    return head;
}

static string Show(ListNode? n)
{
    var parts = new List<string>();
    for (; n is not null; n = n.Next) parts.Add(n.Value.ToString());
    return string.Join(" -> ", parts);
}

// Two pointers, one moving twice as fast. When fast runs out, slow is halfway.
static ListNode? Middle(ListNode? head, bool secondOfTwo)
{
    ListNode? slow = head, fast = head;
    while (secondOfTwo
        ? fast is not null && fast.Next is not null            // stops later
        : fast?.Next is not null && fast.Next.Next is not null) // stops earlier
    {
        slow = slow!.Next;
        fast = fast!.Next!.Next;
    }
    return slow;
}

foreach (int[] vals in new[] { new[] { 1, 2, 3, 4, 5 }, new[] { 1, 2, 3, 4, 5, 6 } })
{
    var head = Build(vals);
    Console.WriteLine($"{Show(head),-24}  length {vals.Length}");
    Console.WriteLine($"    first of two  -> {Middle(head, false)!.Value}");
    Console.WriteLine($"    second of two -> {Middle(head, true)!.Value}");
}

Console.WriteLine("\nOdd length has one middle and both agree. Even length has two,");
Console.WriteLine("and the loop condition alone decides which one you get.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

Imprime:

1 -> 2 -> 3 -> 4 -> 5     length 5
    first of two  -> 3
    second of two -> 3
1 -> 2 -> 3 -> 4 -> 5 -> 6  length 6
    first of two  -> 3
    second of two -> 4

Odd length has one middle and both agree. Even length has two,
and the loop condition alone decides which one you get.

El detalle que la gente equivoca es que una lista de longitud par tiene dos medios, y nada en el código dice cuál quieres — la condición del bucle lo decide sola. while (fast?.Next is not null && fast.Next.Next is not null) se detiene antes y te da el primero; while (fast is not null && fast.Next is not null) te da el segundo.

Lee bien el enunciado del problema, y después elige la condición. No elijas una condición y cruces los dedos.

Costo: O(n) tiempo, O(1) espacio, una sola pasada.

Úsalo cuando necesites el medio, o necesites partir una lista por la mitad — el merge sort sobre una lista enlazada empieza aquí.

Patrón 52 — Detección de ciclos de Floyd

¿La lista se cierra sobre sí misma? Un HashSet<ListNode> lo responde con O(n) de memoria. Dos punteros lo responden sin nada.

// Build a list whose tail loops back to index `enterAt`, or -1 for no cycle.
static ListNode Build(int n, int enterAt)
{
    var nodes = new ListNode[n];
    for (int i = 0; i < n; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < n - 1; i++) nodes[i].Next = nodes[i + 1];
    if (enterAt >= 0) nodes[n - 1].Next = nodes[enterAt];
    return nodes[0];
}

static bool HasCycle(ListNode head, bool trace)
{
    ListNode? slow = head, fast = head;
    int step = 0;
    while (fast is not null && fast.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        step++;
        if (trace) Console.WriteLine($"  step {step}: slow at {slow!.Value}, fast at {(fast is null ? "off the end" : fast.Value.ToString())}");
        if (ReferenceEquals(slow, fast))
        {
            if (trace) Console.WriteLine($"  they are the same node -> cycle");
            return true;
        }
    }
    if (trace) Console.WriteLine("  fast ran off the end -> no cycle");
    return false;
}

Console.WriteLine("6 nodes, tail links back to index 2 (the node holding 3):");
Console.WriteLine($"  cycle: {HasCycle(Build(6, 2), true)}");

Console.WriteLine("\n6 nodes, no cycle:");
Console.WriteLine($"  cycle: {HasCycle(Build(6, -1), true)}");

Console.WriteLine("\nWhy they must meet: inside the cycle, fast gains exactly one place on slow");
Console.WriteLine("per step. A gap that shrinks by one every step reaches zero. It cannot");
Console.WriteLine("step over slow, because stepping over means the gap went from 1 to -1,");
Console.WriteLine("and it only ever changes by 1.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

Imprime:

6 nodes, tail links back to index 2 (the node holding 3):
  step 1: slow at 2, fast at 3
  step 2: slow at 3, fast at 5
  step 3: slow at 4, fast at 3
  step 4: slow at 5, fast at 5
  they are the same node -> cycle
  cycle: True

6 nodes, no cycle:
  step 1: slow at 2, fast at 3
  step 2: slow at 3, fast at 5
  step 3: slow at 4, fast at off the end
  fast ran off the end -> no cycle
  cycle: False

Why they must meet: inside the cycle, fast gains exactly one place on slow
per step. A gap that shrinks by one every step reaches zero. It cannot
step over slow, because stepping over means the gap went from 1 to -1,
and it only ever changes by 1.

La explicación de siempre es que el puntero rápido le “saca una vuelta” al lento. Eso es cierto y no es una prueba, porque sacar una vuelta no implica de forma obvia caer en el mismo nodo — podría saltárselo.

El argumento real está en las últimas tres líneas de esa salida. Una vez que los dos punteros están dentro del ciclo, cada paso mueve al lento uno y al rápido dos, así que la distancia entre ellos cambia exactamente en uno por paso. Una cantidad que cambia de uno en uno y va hacia cero tiene que tocar cero. No puede saltar de 1 a −1.

Fíjate también en ReferenceEquals en vez de ==. En una clase propia == ya es igualdad de referencia, pero escribirlo explícito dice que querías decir el mismo nodo, no un nodo con el mismo valor — y en el momento en que alguien agregue un override de Equals, la versión explícita sigue funcionando.

Costo: O(n) tiempo, O(1) espacio.

Úsalo cuando algo pueda ciclarse y no puedas pagar un conjunto de visitados. Se generaliza más allá de las listas enlazadas: Happy Number y Find the Duplicate Number son los dos este patrón, con “next” definido por una función en vez de por un puntero.

Patrón 53 — Dónde empieza el ciclo

Detectar un ciclo es la mitad de la pregunta. Encontrar el nodo donde empieza parece que necesita contabilidad, y necesita dos líneas.

Reinicia un puntero a la cabeza. Avanza ambos, de un paso a la vez. Se encuentran en la entrada.

static ListNode Build(int n, int enterAt, out ListNode entry)
{
    var nodes = new ListNode[n];
    for (int i = 0; i < n; i++) nodes[i] = new ListNode(i + 1);
    for (int i = 0; i < n - 1; i++) nodes[i].Next = nodes[i + 1];
    nodes[n - 1].Next = nodes[enterAt];
    entry = nodes[enterAt];
    return nodes[0];
}

int n = 9, enterAt = 3;
ListNode head = Build(n, enterAt, out ListNode realEntry);
int tail = enterAt, cycle = n - enterAt;
Console.WriteLine($"{n} nodes, cycle starts at index {enterAt} (value {realEntry.Value})");
Console.WriteLine($"  L = {tail} nodes before the cycle, C = {cycle} nodes in it\n");

// Phase 1: find any meeting point inside the cycle.
ListNode slow = head, fast = head;
int steps = 0;
do { slow = slow.Next!; fast = fast.Next!.Next!; steps++; }
while (!ReferenceEquals(slow, fast));
Console.WriteLine($"phase 1: met at value {slow.Value} after {steps} steps");
Console.WriteLine($"  slow travelled {steps}, fast travelled {steps * 2}");
Console.WriteLine($"  fast went round the cycle {(steps * 2 - steps) / cycle} extra time(s)\n");

// Phase 2: reset one pointer to the head, then advance BOTH one at a time.
ListNode a = head;
int walk = 0;
while (!ReferenceEquals(a, slow)) { a = a.Next!; slow = slow.Next!; walk++; }
Console.WriteLine($"phase 2: reset one to head, step both by 1");
Console.WriteLine($"  met again after {walk} steps, at value {a.Value}");
Console.WriteLine($"  correct: {ReferenceEquals(a, realEntry)}");

Console.WriteLine($"\nWhy: at the meeting point slow has walked L + k, and fast twice that.");
Console.WriteLine($"So 2(L + k) = L + k + nC, giving L + k = nC, so L = nC - k.");
Console.WriteLine($"Walking L more steps from the meeting point lands exactly on the entry.");
Console.WriteLine($"Here L = {tail} and the phase-2 walk took {walk} steps.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

Imprime:

9 nodes, cycle starts at index 3 (value 4)
  L = 3 nodes before the cycle, C = 6 nodes in it

phase 1: met at value 7 after 6 steps
  slow travelled 6, fast travelled 12
  fast went round the cycle 1 extra time(s)

phase 2: reset one to head, step both by 1
  met again after 3 steps, at value 4
  correct: True

Why: at the meeting point slow has walked L + k, and fast twice that.
So 2(L + k) = L + k + nC, giving L + k = nC, so L = nC - k.
Walking L more steps from the meeting point lands exactly on the entry.
Here L = 3 and the phase-2 walk took 3 steps.

Eso parece un truco hasta que escribes la aritmética. Sea L la cantidad de nodos antes del ciclo y C la longitud del ciclo. En el punto de encuentro, el lento ha dado L + k pasos para algún k dentro del ciclo, y el rápido ha dado el doble. El rápido además dio n vueltas extra, así que:

2(L + k) = L + k + nC
    L + k = nC
        L = nC − k

Caminar L pasos más desde el punto de encuentro cubre k + L = nC pasos en total — un número entero de vueltas — así que cae exactamente en la entrada. En la corrida de arriba L = 3 y la segunda fase tomó exactamente 3 pasos.

Costo: O(n) tiempo, O(1) espacio.

Úsalo cuando el problema pregunte dónde empieza el ciclo, o pida el valor duplicado en un arreglo de n+1 valores de 1..n — que es este patrón con el arreglo como función “next”.

Patrón 54 — Invertir en el lugar

Tres punteros, y una línea que tiene que ir primero.

static ListNode? Build(params int[] v)
{
    ListNode? head = null;
    for (int i = v.Length - 1; i >= 0; i--) head = new ListNode(v[i], head);
    return head;
}
static string Show(ListNode? n)
{
    var p = new List<string>();
    for (; n is not null; n = n.Next) p.Add(n.Value.ToString());
    return string.Join(" -> ", p);
}

// Three pointers. Every step re-points ONE arrow backwards.
static ListNode? Reverse(ListNode? head, bool trace)
{
    ListNode? prev = null, cur = head;
    while (cur is not null)
    {
        ListNode? next = cur.Next;      // save it FIRST — the next line destroys it
        cur.Next = prev;                // flip the arrow
        prev = cur;                     // shuffle both forward
        cur = next;
        if (trace) Console.WriteLine($"    reversed=[{Show(prev)}]   remaining=[{Show(cur)}]");
    }
    return prev;                        // cur is null; prev is the new head
}

Console.WriteLine($"start: {Show(Build(1, 2, 3, 4, 5))}");
Console.WriteLine("reversing:");
var r = Reverse(Build(1, 2, 3, 4, 5), true);
Console.WriteLine($"result: {Show(r)}\n");

// Reverse only positions m..n (1-based). The dummy head removes the special
// case where m == 1 and the list head itself changes.
static ListNode? ReverseBetween(ListNode? head, int m, int n)
{
    var dummy = new ListNode(0, head);
    ListNode before = dummy;
    for (int i = 1; i < m; i++) before = before.Next!;

    ListNode? prev = null, cur = before.Next;
    for (int i = 0; i <= n - m; i++)
    {
        ListNode? next = cur!.Next;
        cur.Next = prev; prev = cur; cur = next;
    }
    before.Next!.Next = cur;    // the old first node is now last in the section
    before.Next = prev;         // and prev is now first
    return dummy.Next;
}

Console.WriteLine($"reverse positions 2..4: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 2, 4))}");
Console.WriteLine($"reverse positions 1..5: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 1, 5))}");
Console.WriteLine($"reverse positions 1..1: {Show(ReverseBetween(Build(1, 2, 3, 4, 5), 1, 1))}");

// In groups of k, leaving any short final group alone.
static ListNode? ReverseKGroup(ListNode? head, int k)
{
    ListNode? check = head;
    for (int i = 0; i < k; i++) { if (check is null) return head; check = check.Next; }

    ListNode? prev = null, cur = head;
    for (int i = 0; i < k; i++) { ListNode? nx = cur!.Next; cur.Next = prev; prev = cur; cur = nx; }
    head!.Next = ReverseKGroup(cur, k);   // head is now the tail of this group
    return prev;
}

Console.WriteLine();
foreach (int k in new[] { 2, 3, 5, 6 })
    Console.WriteLine($"k={k}: {Show(ReverseKGroup(Build(1, 2, 3, 4, 5), k))}");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

Imprime:

start: 1 -> 2 -> 3 -> 4 -> 5
reversing:
    reversed=[1]   remaining=[2 -> 3 -> 4 -> 5]
    reversed=[2 -> 1]   remaining=[3 -> 4 -> 5]
    reversed=[3 -> 2 -> 1]   remaining=[4 -> 5]
    reversed=[4 -> 3 -> 2 -> 1]   remaining=[5]
    reversed=[5 -> 4 -> 3 -> 2 -> 1]   remaining=[]
result: 5 -> 4 -> 3 -> 2 -> 1

reverse positions 2..4: 1 -> 4 -> 3 -> 2 -> 5
reverse positions 1..5: 5 -> 4 -> 3 -> 2 -> 1
reverse positions 1..1: 1 -> 2 -> 3 -> 4 -> 5

k=2: 2 -> 1 -> 4 -> 3 -> 5
k=3: 3 -> 2 -> 1 -> 4 -> 5
k=5: 5 -> 4 -> 3 -> 2 -> 1
k=6: 1 -> 2 -> 3 -> 4 -> 5

ListNode? next = cur.Next; tiene que ir antes de cur.Next = prev;. La segunda línea destruye el único puntero al resto de la lista. Invierte las dos y no hay excepción ni caída — la lista simplemente termina antes, y parece un error de lógica en otra parte completamente distinta.

Al final, cur es null y prev es la nueva cabeza. Devolver cur es el otro resbalón clásico.

La versión de sublista muestra por qué importa la cabeza ficticia, que es el siguiente patrón. ReverseBetween(list, 1, 5) invierte desde el primer nodo, así que la cabeza de la lista cambia — y con una ficticia adelante, eso no es un caso especial en absoluto. Fíjate que 1..1 correctamente no hace nada.

La versión por grupos de k hace recursión sobre lo que queda. Después de invertir un grupo, head es la cola de ese grupo, que es exactamente donde se engancha el siguiente grupo.

Costo: O(n) tiempo, O(1) espacio para las versiones iterativas.

Úsalo cuando necesites invertir una lista, invertirla en parte, rotarla, o comprobar si es un palíndromo — eso último es el patrón 51 para encontrar el medio, y después este para invertir la mitad de atrás.

Patrón 55 — La cabeza ficticia

Un nodo que no guarda nada, puesto delante de la lista real, solo para que “el primer nodo” nunca sea un caso especial.

static ListNode? Build(params int[] v)
{
    ListNode? head = null;
    for (int i = v.Length - 1; i >= 0; i--) head = new ListNode(v[i], head);
    return head;
}
static string Show(ListNode? n)
{
    var p = new List<string>();
    for (; n is not null; n = n.Next) p.Add(n.Value.ToString());
    return p.Count == 0 ? "(empty)" : string.Join(" -> ", p);
}

// WITHOUT a dummy head: the first node is a special case, because there is no
// previous node to attach it to.
static ListNode? MergeAwkward(ListNode? a, ListNode? b)
{
    if (a is null) return b;
    if (b is null) return a;

    ListNode head, tail;
    if (a.Value <= b.Value) { head = tail = a; a = a.Next; }
    else                    { head = tail = b; b = b.Next; }

    while (a is not null && b is not null)
    {
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else                    { tail.Next = b; b = b.Next; }
        tail = tail.Next!;
    }
    tail.Next = a ?? b;
    return head;
}

// WITH a dummy head: no special case at all. Every node is attached the same way.
static ListNode? Merge(ListNode? a, ListNode? b)
{
    var dummy = new ListNode(0);
    ListNode tail = dummy;

    while (a is not null && b is not null)
    {
        if (a.Value <= b.Value) { tail.Next = a; a = a.Next; }
        else                    { tail.Next = b; b = b.Next; }
        tail = tail.Next!;
    }
    tail.Next = a ?? b;      // whichever still has nodes; both null is fine too
    return dummy.Next;       // the real head, whatever it turned out to be
}

Console.WriteLine($"a = {Show(Build(1, 3, 5, 7))}");
Console.WriteLine($"b = {Show(Build(2, 3, 6))}");
Console.WriteLine($"merged (dummy head) = {Show(Merge(Build(1, 3, 5, 7), Build(2, 3, 6)))}");
Console.WriteLine($"merged (awkward)    = {Show(MergeAwkward(Build(1, 3, 5, 7), Build(2, 3, 6)))}");
Console.WriteLine();
Console.WriteLine($"empty + [1,2]  = {Show(Merge(null, Build(1, 2)))}");
Console.WriteLine($"empty + empty  = {Show(Merge(null, null))}");
Console.WriteLine();
Console.WriteLine("The dummy version is four lines shorter and has no branch for the");
Console.WriteLine("first node. Both null works too, because dummy.Next was never set.");

class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}

Imprime:

a = 1 -> 3 -> 5 -> 7
b = 2 -> 3 -> 6
merged (dummy head) = 1 -> 2 -> 3 -> 3 -> 5 -> 6 -> 7
merged (awkward)    = 1 -> 2 -> 3 -> 3 -> 5 -> 6 -> 7

empty + [1,2]  = 1 -> 2
empty + empty  = (empty)

The dummy version is four lines shorter and has no branch for the
first node. Both null works too, because dummy.Next was never set.

Las dos funciones de ese programa producen la misma salida. La diferencia es que la incómoda necesita una rama para decidir la cabeza antes de que el bucle pueda empezar, y después repite la comparación que acaba de hacer. La versión con ficticia engancha cada nodo de la misma forma y devuelve dummy.Next al final — sea lo que sea que haya resultado.

También maneja los casos vacíos gratis. Merge(null, null) devuelve dummy.Next, que nunca se asignó, que es null. Sin guardas.

Costo: un nodo extra, y es basura en el momento en que retornas.

Úsalo cuando una operación sobre la lista pueda cambiar la cabeza — fusionar, borrar un nodo, quitar el n-ésimo desde el final, particionar alrededor de un valor. Si te descubres escribiendo if (head == null) seguido de una primera iteración duplicada, esa es la señal.

Qué recordar

• LinkedList<T> es doblemente enlazada y no es de lo que hablan estos problemas. Declara un ListNode de cuatro líneas y sigue adelante.

• La condición del bucle del puntero rápido elige qué medio obtienes. En una lista de longitud par hay dos, y el código no dice de otra forma cuál querías.

• La prueba de que Floyd termina es que la distancia cambia exactamente en uno. No “en algún momento le saca una vuelta” — eso no descarta que se lo salte.

• L = nC − k es por qué la fase dos cae en la entrada. Reinicia un puntero a la cabeza, avanza ambos de uno en uno.

• Guarda next antes de sobrescribir cur.Next. Hacerlo al revés trunca la lista en silencio, sin una excepción que señale la línea.

• Devuelve prev, no cur. Al final de una inversión cur es null.

• Una cabeza ficticia borra el caso especial, no solo lo ordena. Si estás escribiendo una rama aparte para el primer nodo, agrega una ficticia y borra la rama.

La parte 12 empieza con árboles: los cuatro órdenes de recorrido, el iterativo que la gente no puede reconstruir bajo presión, y por qué el recorrido por niveles necesita una cola y no ingenio.