Como encontrar o elemento do meio da lista vinculada em uma passagem?

Uma das perguntas mais populares sobre estruturas de dados e algoritmos, principalmente feita em entrevista por telefone.

Trapaceando e fazendo dois passes ao mesmo tempo, em paralelo. Mas não sei se os recrutadores vão gostar disso.

Pode ser feito em uma única lista vinculada, com um bom truque. Dois ponteiros percorrem a lista, um com velocidade dupla. Quando o jejum chega ao fim, o outro está no meio do caminho.

Se não for uma lista duplamente vinculada, você pode apenas contar e usar uma lista, mas isso exige duplicar sua memória na pior das hipóteses, e simplesmente não funcionará se a lista for muito grande para armazenar na memória.

Uma solução simples, quase boba, é apenas incrementar o nó do meio a cada dois nós

function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}

Elaborando a resposta de Hendrik

Se for uma lista duplamente vinculada, itere pelas duas extremidades

function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

Dado [1, 2, 3] => 2

1, 3
1, 2
2, 2

Dado [1, 2] => 1

1, 2
1, 1

Dado [1] => 1

Dado [] => null

Crie uma estrutura com um ponteiro capaz de apontar para nós da lista vinculada e com uma variável inteira que mantenha a contagem do número de nós na lista.

struct LL{
    struct node *ptr;
    int         count;
}start;

$start.ptr$$start.count = 1$
$start.count$

$start.count$

Crie uma matriz dinâmica, na qual cada elemento da matriz é um ponteiro para cada nó da lista em ordem de deslocamento, começando desde o início. Crie um número inteiro, inicializado como 1, que monitore quantos nós você visitou (o que aumenta cada vez que você acessa um novo nó). Quando você chega ao final, sabe o tamanho da lista e tem uma matriz ordenada de ponteiros para cada nó. Por fim, divida o tamanho da lista por 2 (e subtraia 1 para indexação baseada em 0) e busque o ponteiro mantido nesse índice da matriz; se o tamanho da lista for ímpar, você poderá escolher qual elemento retornar (ainda retornarei o primeiro).

Aqui está um código Java que esclarece o assunto (mesmo que a idéia de uma matriz dinâmica seja um pouco instável). Eu forneceria C / C ++, mas estou muito enferrujado nessa área.

public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}

A recursão é considerada mais de uma passagem?

Percorra a lista até o final, passando uma contagem de números inteiros por referência. Faça uma cópia local desse valor em cada nível para referência posterior e aumente a contagem de ref para a próxima chamada.

No último nó, divida a contagem por dois e trunque / floor () o resultado (se você quiser que o primeiro nó seja o "meio" quando houver apenas dois elementos) ou arredonde para cima (se você quiser que o segundo nó seja o meio"). Use um índice baseado em zero ou um adequadamente.

Desenrolando, combine a contagem de ref com a cópia local (que é o número do nó). Se igual, retorne esse nó; caso contrário, retorne o nó retornado da chamada recursiva.
.

Existem outras maneiras de fazer isso; alguns deles podem ser menos pesados ​​(eu pensei ter visto alguém dizer lê-lo em uma matriz e usar o comprimento da matriz para determinar os parabéns do meio). Mas, francamente, não há boas respostas, porque é uma pergunta estúpida para a entrevista. Número um, que ainda usa listas vinculadas ( opinião de apoio ); Segundo, encontrar o nó do meio é um exercício acadêmico arbitrário, sem valor nos cenários da vida real; Terceiro, se eu realmente precisasse conhecer o nó do meio, minha lista vinculada exporia uma contagem de nós. É mais fácil manter essa propriedade do que perder tempo percorrendo a lista inteira toda vez que eu quero o nó do meio. E finalmente, quatro, todo entrevistador vai gostar ou rejeitar respostas diferentes - o que um entrevistador acha que é liso, outro chamará de ridículo.

Quase sempre respondo às perguntas da entrevista com mais perguntas. Se eu receber uma pergunta como essa (nunca a tenho), pergunto: (1) O que você está armazenando nesta lista vinculada e existe uma estrutura mais apropriada para acessar com eficiência o nó do meio, se houver realmente uma necessidade? ; (2) Quais são minhas restrições? Eu posso torná-lo mais rápido se a memória não for um problema (por exemplo, a resposta da matriz), mas se o entrevistador achar que aumentar a memória é um desperdício, eu vou me apegar. (3) Em que idioma eu vou estar desenvolvendo? Quase todas as linguagens modernas que conheço possuem classes integradas para lidar com listas vinculadas que tornam desnecessária a passagem da lista - por que reinventar algo que foi ajustado para eficiência pelos desenvolvedores da linguagem?

Usando 2 ponteiros. Incremente um em cada iteração e outro a cada segunda iteração. Quando o primeiro ponteiro aponta para o final da lista vinculada, o segundo ponteiro aponta para o modo intermediário da lista vinculada.