Как развернуть односвязный список и найти его середину?

Разворот делается одним проходом с тремя указателями (`prev`, `curr`, `next`) за O(n) времени и O(1) памяти, а середина находится техникой быстрого и медленного указателей — тоже за один проход.

Разворот

/** Узел: { val, next }, next — следующий узел или null */
function reverse(head) {
  let prev = null;
  while (head) {
    const next = head.next; // сохраняем хвост до перезаписи
    head.next = prev;
    prev = head;
    head = next;
  }
  return prev; // новая голова
}

Рекурсивный вариант короче, но тратит O(n) стека: на списке из миллиона узлов он упадёт с переполнением.

Середина

• slow шагает на 1, fast на 2; цикл while (fast && fast.next).
• Когда fast дошёл до конца, slow стоит в середине.
• При чётной длине так получается вторая из двух средних; если нужна первая — стартуйте fast с head.next.

Типичные ошибки

• Потерять ссылку на остаток списка, не сохранив next перед перезаписью.
• Не обработать пустой список и список из одного узла.

Коротко для собеседования

Разворот — один проход, в котором next сохраняют до перезаписи указателя: O(n) времени и O(1) памяти, тогда как рекурсия на длинном списке переполнит стек. Середину ищут быстрым и медленным указателями, а вместе эти приёмы решают, например, проверку списка на палиндром без дополнительной памяти.