Listas encadeadas em C#: dois ponteiros em velocidades diferentes

As partes 1 a 10 são padrões de maratona. Daqui em diante a série cobre os de entrevista, e a primeira coisa a dizer sobre listas encadeadas é que você quase nunca vai ver uma numa maratona. O Codeforces te entrega um array. Entrevistas te entregam uma lista encadeada o tempo todo.

A segunda coisa é um problema do C#. LinkedList<T> existe na BCL e é duplamente encadeada, expondo LinkedListNode<T> com Next e Previous. Não é a estrutura de que esses problemas tratam, e usá-la remove a dificuldade em vez de resolvê-la. Todo programa aqui declara o próprio nó:

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

Isso é um construtor primário, e é o tipo inteiro. Todo programa abaixo está completo, rodou no .NET 10, e a saída foi colada da execução.

Padrão 51 — O meio, em uma passada

O jeito óbvio percorre a lista para contá-la, depois percorre metade de novo. Duas passadas, e você precisa do tamanho.

Em vez disso, mova dois ponteiros, um duas vezes mais rápido. Quando o rápido chega ao fim, o lento está no meio.

// 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;
}

Ele 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.

O detalhe que as pessoas erram é que uma lista de tamanho par tem dois meios, e nada no código diz qual você quer — só a condição do laço decide. while (fast?.Next is not null && fast.Next.Next is not null) para mais cedo e te dá o primeiro; while (fast is not null && fast.Next is not null) te dá o segundo.

Leia o enunciado com atenção, depois escolha a condição. Não escolha uma condição e torça.

Custo: O(n) de tempo, O(1) de espaço, uma passada.

Use quando você precisa do meio, ou precisa partir uma lista ao meio — o merge sort numa lista encadeada começa aqui.

Padrão 52 — A detecção de ciclo de Floyd

A lista volta para si mesma? Um HashSet<ListNode> responde isso com O(n) de memória. Dois ponteiros respondem com nenhuma.

// 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;
}

Ele 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.

A explicação de sempre é que o ponteiro rápido “dá uma volta a mais” no lento. Isso é verdade e não é uma prova, porque dar uma volta a mais não implica de forma óbvia cair no mesmo nó — ele poderia passar por cima.

O argumento de verdade está nas três últimas linhas dessa saída. Assim que os dois ponteiros estão dentro do ciclo, cada passo move o lento em um e o rápido em dois, então a distância entre eles muda exatamente um por passo. Uma quantidade que muda de um em um e vai em direção ao zero tem que acertar o zero. Ela não pode pular de 1 para −1.

Repare também no ReferenceEquals em vez de ==. Numa classe própria o == já é igualdade de referência, mas escrever isso explicitamente diz que você quis dizer o mesmo nó, não um nó com o mesmo valor — e no momento em que alguém adiciona um override de Equals, a versão explícita continua funcionando.

Custo: O(n) de tempo, O(1) de espaço.

Use quando qualquer coisa pode ciclar e você não pode pagar um set de visitados. Isso generaliza para além de listas encadeadas: Happy Number e Find the Duplicate Number são os dois esse padrão, com “next” definido por uma função em vez de um ponteiro.

Padrão 53 — Onde o ciclo começa

Detectar o laço é metade da pergunta. Achar o nó onde ele começa parece precisar de contabilidade, e precisa de duas linhas.

Reinicie um ponteiro na cabeça. Avance os dois, um passo de cada vez. Eles se encontram na 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;
}

Ele 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.

Isso parece um truque até você escrever a aritmética. Seja L o número de nós antes do ciclo e C o tamanho do ciclo. No ponto de encontro, o lento deu L + k passos para algum k dentro do ciclo, e o rápido deu o dobro disso. O rápido também deu n voltas extras, então:

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

Andar mais L passos a partir do ponto de encontro cobre k + L = nC passos no total — um número inteiro de voltas — então cai exatamente na entrada. Na execução acima L = 3 e a segunda fase levou exatamente 3 passos.

Custo: O(n) de tempo, O(1) de espaço.

Use quando o problema pergunta onde o ciclo começa, ou pede o valor duplicado num array de n+1 valores de 1..n — que é esse padrão com o array como função “next”.

Padrão 54 — Invertendo in-place

Três ponteiros, e uma linha que tem que vir primeiro.

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;
}

Ele 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; tem que vir antes de cur.Next = prev;. A segunda linha destrói o único ponteiro para o resto da lista. Troque as duas e não há exceção nem crash — a lista simplesmente acaba cedo, e parece um bug de lógica em outro lugar qualquer.

No fim, cur é null e prev é a nova cabeça. Retornar cur é o outro escorregão clássico.

A versão de sublista mostra por que o dummy head importa, que é o próximo padrão. ReverseBetween(list, 1, 5) inverte a partir do primeiro nó, então a cabeça da lista muda — e com um dummy na frente, isso não é caso especial nenhum. Repare que 1..1 corretamente não faz nada.

A versão em grupos de k recursa no restante. Depois de inverter um grupo, head é a cauda daquele grupo, que é exatamente onde o próximo grupo se prende.

Custo: O(n) de tempo, O(1) de espaço para as versões iterativas.

Use quando você precisa de uma lista invertida, invertida em parte, rotacionada, ou testada para ser um palíndromo — esse último é o padrão 51 para achar o meio, e depois esse aqui para inverter a metade de trás.

Padrão 55 — O dummy head

Um nó que não guarda nada, sentado na frente da lista de verdade, só para que “o primeiro nó” nunca seja um 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;
}

Ele 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.

As duas funções desse programa produzem saída idêntica. A diferença é que a desajeitada precisa de um desvio para decidir a cabeça antes de o laço começar, e depois repete a comparação que acabou de fazer. A versão com dummy prende todo nó do mesmo jeito e retorna dummy.Next no fim — seja lá o que ele tenha virado.

Ela também trata os casos vazios de graça. Merge(null, null) retorna dummy.Next, que nunca foi atribuído, que é null. Nenhuma guarda necessária.

Custo: um nó extra, e ele vira lixo no momento em que você retorna.

Use quando uma operação na lista pode mudar a cabeça — mesclar, apagar um nó, remover o n-ésimo a partir do fim, particionar em torno de um valor. Se você se pegar escrevendo if (head == null) seguido de uma primeira iteração duplicada, esse é o sinal.

O que lembrar

• LinkedList<T> é duplamente encadeada e não é o que esses problemas querem dizer. Declare um ListNode de quatro linhas e siga em frente.

• A condição do laço do ponteiro rápido escolhe qual meio você pega. Numa lista de tamanho par existem dois, e o código não diz de outro jeito qual você queria.

• A prova de que o Floyd termina é que a distância muda exatamente um. Não “ele dá uma volta a mais em algum momento” — isso não descarta passar por cima.

• L = nC − k é por que a fase dois cai na entrada. Reinicie um ponteiro na cabeça, avance os dois de um em um.

• Salve o next antes de sobrescrever cur.Next. Fazer isso ao contrário trunca a lista em silêncio, sem exceção nenhuma para apontar a linha.

• Retorne prev, não cur. No fim de uma inversão cur é null.

• Um dummy head apaga o caso especial, não só o arruma. Se você está escrevendo um desvio separado para o primeiro nó, adicione um dummy e apague o desvio.

A parte 12 começa nas árvores: os quatro percursos, o iterativo que as pessoas não conseguem reconstruir sob pressão, e por que o percurso por níveis precisa de uma fila em vez de esperteza.