Quero explicar uma técnica simples e eficaz que você pode usar em uma entrevista ao lidar com Arrays, Strings, Linked Lists, etc. estruturas.

Vamos começar pela teoria. Existem dois casos de uso comuns deste algoritmo:

• esquerda/direita O conceito central deste algoritmo é ter duas variáveis ​​inteiras que se moverão de ambos os lados de uma string ou array. Normalmente, as pessoas chamam isso de esquerda e direita. A esquerda passará do índice 0 para o comprimento - 1, e a direita será o oposto.

• lento/rápido Ponteiros correm na mesma direção, por exemplo, do início ao fim, mas um ponteiro corre mais rápido que outro. Nesse caso, as pessoas costumam chamar variáveis ​​de lentas e rápidas.

Algoritmos são elementares e a melhor maneira de entendê-los é examinar alguns exemplos.

Primeiro, vamos ver um caso com ponteiros para a esquerda e para a direita. Aqui está um exemplo elementar de um problema que podemos resolver usando este algoritmo. O objetivo é claro: queremos encontrar um par cuja soma seja igual a um determinado número.
A abordagem de força bruta criará loops aninhados, mas há uma baixa chance de passar na entrevista usando-a.
Uma abordagem melhor seria usar o algoritmo de dois ponteiros e encontrá-lo em um loop para ter complexidade O(n) em vez de O(n²)

const findPair = (arr, target) => {
    let left = 0;                 // Start with two pointers left from start, right, from the end
    let right = arr.length - 1;

    while (left 

Vamos mudar para uma abordagem em que os ponteiros têm velocidades diferentes. É um problema frequente que você pode encontrar em uma entrevista. Você precisa encontrar o meio da lista vinculada fornecida.

A abordagem de força bruta não é tão ruim quanto o exemplo anterior, mas o entrevistador espera uma abordagem melhor.

Com o algoritmo de dois ponteiros, você resolverá este problema com complexidade O(n), enquanto a abordagem de força bruta levará O(2n) se você usar dois loops sequenciais.


class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

const findMiddle = (head) => {
    if (!head) return null;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;           // Move slow pointer one step
        fast = fast.next.next;      // Move fast pointer two steps
    }

    return slow;  // Slow pointer will be at the middle
}

// Creating a linked list 1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);

head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

findMiddle(head).value);  // Output: 3 (middle node)