Je souhaite expliquer une technique simple et efficace que vous pouvez utiliser lors d'un entretien lorsque vous traitez des tableaux, des chaînes, des listes chaînées, etc. Cela améliorera également vos connaissances fondamentales sur ces données. structures.

Commençons par la théorie. Il existe deux cas d'utilisation courants de cet algorithme :

• gauche/droite Le concept central de cet algorithme est d'avoir deux variables entières qui se déplaceront des deux côtés d'une chaîne ou d'un tableau. Habituellement, les gens l'appellent à gauche et à droite. La gauche se déplacera de l'indice 0 à la longueur — 1, et la droite est l'opposé.

• lent/rapide Les pointeurs courent dans la même direction, par exemple du début à la fin, mais un pointeur court plus vite qu'un autre. Dans ce cas, les gens appellent généralement les variables lentement et rapidement.

Les algorithmes sont élémentaires, et la meilleure façon de les comprendre est d'examiner quelques exemples.

Tout d’abord, examinons un cas avec des pointeurs gauche et droit. Voici un exemple élémentaire de problème que nous pouvons résoudre en utilisant cet algorithme. Le but est clair : nous voulons trouver une paire dont la somme sera égale à un nombre donné.
L'approche par force brute créera des boucles imbriquées, mais il y a peu de chances de réussir l'entretien en l'utilisant.
Une meilleure approche serait d'utiliser l'algorithme à deux pointeurs et de le trouver dans une boucle pour avoir une complexité O(n) au lieu 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 

Passons à une approche où les pointeurs ont des vitesses différentes. C’est un problème fréquent que l’on peut rencontrer lors d’un entretien. Vous devez trouver le milieu de la liste chaînée donnée.

L'approche par force brute n'est pas aussi mauvaise que l'exemple précédent, mais l'intervieweur s'attend à une meilleure.

Avec l'algorithme à deux pointeurs, vous résoudrez ce problème avec une complexité O(n), alors que l'approche par force brute prendra O(2n) si vous utilisez deux boucles séquentielles.


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)