Quiero explicarte una técnica sencilla y eficaz que puedes utilizar en una entrevista cuando trates con Arrays, Strings, Linked Lists, etc. Esto también mejorará tus conocimientos fundamentales sobre estos datos. estructuras.

Comencemos por la teoría. Hay dos casos de uso comunes de este algoritmo:

• izquierda/derecha El concepto central de este algoritmo es tener dos variables enteras que se moverán desde ambos lados de una cadena o matriz. Por lo general, la gente lo llama izquierda y derecha. La izquierda se moverá desde el índice 0 a la longitud - 1, y la derecha es lo opuesto.

• Los punteros lentos/rápidos se ejecutan en la misma dirección, por ejemplo, de principio a fin, pero un puntero se ejecuta más rápido que otro. En este caso, la gente suele llamar a las variables lentas y rápidas.

Los algoritmos son elementales y la mejor manera de entenderlos es mirar algunos ejemplos.

Primero, veamos un caso con punteros izquierdo y derecho. Aquí hay un ejemplo elemental de un problema que podemos resolver usando este algoritmo. El objetivo es claro: queremos encontrar un par cuya suma sea igual a un número determinado.
El enfoque de fuerza bruta creará bucles anidados, pero hay pocas posibilidades de pasar la entrevista usándolo.
Un mejor enfoque sería utilizar el algoritmo de dos punteros y encontrarlo en un bucle para que tenga complejidad O(n) en lugar 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 

Pasemos a un enfoque en el que los punteros tienen diferentes velocidades. Es un problema frecuente que puedes encontrar en una entrevista. Debe encontrar el centro de la lista vinculada proporcionada.

El enfoque de fuerza bruta no es tan malo como el ejemplo anterior, pero el entrevistador espera uno mejor.

Con el algoritmo de dos punteros, resolverá este problema con una complejidad O(n), mientras que el enfoque de fuerza bruta tomará O(2n) si usa dos bucles secuenciales.


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)