Медленный бегун в конце концов встретится с быстрым бегуном на круговой дорожке…
В первый раз, когда я увидел 142. Linked List Cycle II, я ставлю лишнее значение visited
в каждый из узлов, чего нельзя допускать и это также занимает больше памяти.
Лучшим решением является использование двух указателей, которые я хотел бы назвать «два бегуна», потому что это помогает мне представить это в моей голове. Представьте, что есть два бегуна, и если они продолжат бежать по круговой дорожке, то в какой-то момент встретятся. Если дорожка не круглая, они никогда не смогут встретиться друг с другом.
С учетом этого 141. Linked List Cycle было бы очень просто.
141. Цикл связанного списка
Учитывая связанный список, определите, есть ли в нем цикл.
Чтобы представить цикл в данном связанном списке, мы используем целое число
pos
, которое представляет позицию (с индексом 0) в связанном списке, к которой соединяется хвост. Еслиpos
равно-1
, то в связанном списке нет цикла.
var hasCycle = function(head) { if(!head || !head.next || !head.next.next) return false; let fast = head.next.next; let slow = head.next; while(fast !== slow){ if(!fast.next || !fast.next.next) return false; fast = fast.next.next; slow = slow.next; } return true; };
Нам просто нужно настроить указатель fast
и slow
и посмотреть, могут ли они быть равными в какой-то момент. Есть мелкие вещи, требующие внимания.
- нам нужно проверить первые 3 узла, прежде чем двигаться дальше.
- мы не можем установить
fast
иslow
вhead
в качестве начальных значений, потому что они никогда не попадут в цикл. - в цикле нам нужно проверить еще 2 узла на
fast
.
142. Цикл связанного списка II
Учитывая связанный список, верните узел, с которого начинается цикл. Если цикла нет, вернуть
null
.
Чтобы представить цикл в данном связанном списке, мы используем целое число
pos
, которое представляет позицию (с индексом 0) в связанном списке, к которой соединяется хвост. Еслиpos
равно-1
, то в связанном списке нет цикла.
Эта проблема среднего уровня движется глубже, что требует не только логического значения, но и точного индекса начала цикла.
Обратите внимание, что fast
и slow
встречаются в любых узлах цикла, откуда мы знаем, где он начинается?
Когда fast
и slow
встречаются в P
, мы знаем, что fast
пробежал m
круг, а slow
пробежал n
круга.
fDis = a + (b+c)*m + b sDis = a + (b+c)*n + b
Поскольку fast
работает в два раза быстрее, чем slow
, fDis = 2 *sDis
.
И мы также знаем, что P = a + b
и R = a
.
Таким образом, мы можем легко получить a + b = (b+c)(m-2n)
, что означает, что если бегун пробежит a + b
, другой бегун пробежит несколько кругов. Итак, если мы поместим один указатель p1
в новичок, а другой указатель p2
в P
(где встретились fast
и slow
), p1
и p2
встретятся в R
(где начинается цикл).
var detectCycle = function(head) { if(!head || !head.next || !head.next.next) return null; let fast = head.next.next; let slow = head.next; while(fast !== slow){ if(!fast.next || !fast.next.next) return null; fast = fast.next.next; slow = slow.next; } let p1 = fast; let p2 = head; while(p1 !== p2){ p1 = p1.next; p2 = p2.next; } return p1; };
Когда я писал код, я допустил несколько ошибок, вызванных «ошибкой времени выполнения» или бесконечным циклом. Поднимите голову, когда вы это сделаете.
- Приходится устанавливать первые шаги как для
fast
, так и дляslow
. Я установил толькоfast
и сделалslow = head
, что не работает, потому чтоfDis !== 2 * sDis
. - Не забывайте проверять
fast.next
при проверкеfast.next.next
.
Развлекайся!