Я хочу объяснить простой и эффективный метод, который вы можете использовать на собеседовании при работе с массивами, строками, связанными списками и т. д. Это также улучшит ваши фундаментальные знания об этих данных. структуры.

Начнем с теории. Существует два распространенных варианта использования этого алгоритма:

• left/right Основная идея этого алгоритма — наличие двух целочисленных переменных, которые будут перемещаться с обеих сторон строки или массива. Обычно люди называют это левым и правым. Левая переместится от индекса 0 к длине — 1, а правая — наоборот.

• медленно/быстро Указатели перемещаются в одном направлении, например, от начала до конца, но один указатель движется быстрее другого. В этом случае люди обычно называют переменные медленными и быстрыми.

Алгоритмы элементарны, и лучший способ понять их — рассмотреть несколько примеров.

Во-первых, давайте рассмотрим случай с указателями влево и вправо. Вот элементарный пример проблемы, которую мы можем решить с помощью этого алгоритма. Цель ясна: мы хотим найти пару, сумма которой будет равна заданному числу.
Подход грубой силы создаст вложенные циклы, но вероятность прохождения собеседования с его помощью невелика.
Лучшим подходом было бы использовать алгоритм двух указателей и найти его в одном цикле со сложностью O(n) вместо 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 

Давайте перейдем к подходу, при котором указатели имеют разную скорость. Это частая проблема, с которой можно встретиться на собеседовании. Вам нужно найти середину данного связанного списка.

Подход грубой силы не так плох, как предыдущий пример, но интервьюер ожидает лучшего.

С помощью алгоритма двух указателей вы решите эту проблему со сложностью O(n), тогда как метод грубой силы потребует O(2n), если вы используете два последовательных цикла.


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)