Быстрый и медленный пойнтер

Метод быстрых и медленных указателей — это реализация техники двух указателей. Идея состоит в том, чтобы иметь два указателя, которые не двигаются синхронно. Это может означать, что они движутся с разной "скоростью" во время итерации, начинают движение из разных мест или обладают какой-либо другой абстрактной разницей.

Когда указатели движутся с разной скоростью, обычно "быстрый" указатель перемещается на два узла за итерацию, а "медленный" — на один узел (хотя это не всегда так).
Вот пример псевдокода:

// head is the head node of a linked list
function fn(head):
    slow = head
    fast = head

    while fast and fast.next:
        Do something here
        slow = slow.next
        fast = fast.next.next

Причина, по которой в условии while нужно проверять fast.next, заключается в том, что если fast находится на последнем узле, то fast.next будет null. Попытка доступа к fast.next.next вызовет ошибку, так как это будет равносильно попытке сделать null.next.

Рассмотрим примеры, где полезно использовать быстрые и медленные указатели.

Пример

Дан head — начало связного списка с нечетным количеством узлов. Нужно вернуть значение узла, находящегося в середине списка.

Например, для связного списка, который представляет 1 -> 2 -> 3 -> 4 -> 5, ответом будет 3.

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

function fn(head):
    array = int[]
    while head:
        array.push(head.val)
        head = head.next

    return array[array.length // 2]

Такое решение можно считать "читерским", и оно не будет принято как допустимое на собеседовании.
Возможно, вы заметили, что сложность этой задачи заключается в том, что мы не знаем длину связного списка. Один из возможных подходов — это сначала пройти по списку с временным указателем, чтобы определить его длину, а затем, зная длину, снова пройти от начала, чтобы найти средний элемент.

let getMiddle = (head) => {
  let length = 0;
  let dummy = head;
  while (dummy) {
    length++;
    dummy = dummy.next;
  }

  for (let i = 0; i < Math.floor(length / 2); i++) {
    head = head.next;
  }

  return head.val;
};

Наиболее элегантное решение заключается в использовании техники быстрых и медленных указателей. Если один указатель движется в два раза быстрее другого, то, когда он достигнет конца списка, медленный указатель окажется на середине, так как он движется в два раза медленнее.

let getMiddle = (head) => {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow.val;
};

Задачи
https://leetcode.com/problems/linked-list-cycle/description/
https://leetcode.com/problems/middle-of-the-linked-list/description/
https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/
https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/