Ich möchte Ihnen eine einfache und effektive Technik erläutern, die Sie in einem Vorstellungsgespräch beim Umgang mit Arrays, Strings, verknüpften Listen usw. anwenden können. Dadurch verbessern Sie auch Ihr grundlegendes Wissen über diese Daten Strukturen.

Beginnen wir mit der Theorie. Es gibt zwei häufige Anwendungsfälle dieses Algorithmus:

• left/right Das zentrale Konzept dieses Algorithmus besteht darin, zwei ganzzahlige Variablen zu haben, die sich von beiden Seiten eines Strings oder Arrays bewegen. Normalerweise nennen die Leute es links und rechts. Die linke Seite bewegt sich vom Index 0 zur Länge 1, die rechte Seite ist das Gegenteil.

• langsam/schnell Zeiger laufen in die gleiche Richtung, z. B. vom Anfang bis zum Ende, aber ein Zeiger läuft schneller als ein anderer. In diesem Fall werden Variablen normalerweise als langsam und schnell bezeichnet.

Algorithmen sind elementar und der beste Weg, sie zu verstehen, besteht darin, sich einige Beispiele anzusehen.

Schauen wir uns zunächst einen Fall mit Links- und Rechtszeigern an. Hier ist ein einfaches Beispiel für ein Problem, das wir mit diesem Algorithmus lösen können. Das Ziel ist klar: Wir wollen ein Paar finden, dessen Summe einer bestimmten Zahl entspricht.
Der Brute-Force-Ansatz erzeugt verschachtelte Schleifen, aber die Chance, das Interview damit zu bestehen, ist gering.
Ein besserer Ansatz wäre, den Zwei-Zeiger-Algorithmus zu verwenden und in einer Schleife zu finden, dass er eine O(n)-Komplexität anstelle von O(n²) hat

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 

Lassen Sie uns zu einem Ansatz wechseln, bei dem Zeiger unterschiedliche Geschwindigkeiten haben. Es ist ein häufiges Problem, auf das man in einem Vorstellungsgespräch stoßen kann. Sie müssen die Mitte der angegebenen verknüpften Liste finden.

Der Brute-Force-Ansatz ist nicht so schlimm wie das vorherige Beispiel, aber der Interviewer erwartet einen besseren.

Mit dem Zwei-Zeiger-Algorithmus lösen Sie dieses Problem mit einer Komplexität von O(n), wohingegen der Brute-Force-Ansatz O(2n) erfordert, wenn Sie zwei aufeinanderfolgende Schleifen verwenden.


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)