Проблема

Учитывая head односвязного списка, вернуть средний узел связанного списка.

Если есть два средних узла, верните второй средний узел.

Пример 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Решение

Ключ к этой проблеме в том, что вы догадались; два указателя. Связанные списки иногда сложно визуализировать, но с практикой это определенно становится легче.

  1. Первый указатель будет перемещаться по связанному списку со скоростью «x», а второй указатель будет проходить по связанному списку со скоростью «2x».
  2. Завершение цикла произойдет в одном из двух случаев: либо второй указатель равен нулю (связный список четной длины), либо следующее значение второго указателя равно нулю (связный список нечетной длины).
  3. Возвращает значение первого указателя, также известного как вторая половина связанного списка.