Есть ли в связанном списке цикл?

Question

Я застрял в следующей проблеме Leetcode.

По данным односвязного списка определить, существует ли цикл. Если это так, верните True. В противном случае верните False.

Мои рассуждения: разрешить двум указателям go по всему единому связанному списку. Один из указателей перемещает один узел за раз, в то время как другой указатель будет касаться каждого другого узла. Если существует цикл, указатели в конечном итоге встретятся.

Вот моя попытка (в python):

# Edge Case
if head == None:
    return False
currA = head
currB = head

while currA and currB:
    currA = currA.next
    if currB.next:
        currB = currB.next.next
    if currA == None or currB == None:
        return False
    if currA == currB:
        return True
return False

Я отправил этот код в leetcode и смог передать все тестовые случаи, за исключением очень длинного.

Однако следующий код отлично работает (написанный кем-то другим):

if not head or not head.next: return False        
slow, fast = head, head.next
while slow != fast:
    if not fast or not fast.next: return False
    slow, fast = slow.next, fast.next.next
return True

Для меня главное отличие - это условие оператора while. Тем не менее, я все еще не вижу ошибку в моем коде.

Answer 1

Есть два других различия между этими двумя решениями. Первый тривиален; ваше решение инициализирует currB = head, тогда как переменная fast другого решения инициализируется как head.next. Это почти не должно влиять на работу алгоритма.

Разница в том, что ваше решение оставляет currB неизменным, когда currB.next равно None. Другое решение завершает в этом случае, возвращая False, но ваш будет сидеть с currB на последнем узле, без изменений, в то время как currA продвигается к концу списка. В конце концов, currA достигает последнего узла, и в этот момент currA и currB равны; поэтому ваш алгоритм думает, что он обнаружил цикл, но на самом деле это потому, что ваш currB указатель перестал двигаться вперед, а другой перехватил его.

Эта проблема возникает не для всех нециклических c список; только когда currB заканчивается как последний узел. Это зависит от четности длины списка, так как currB продвигается на два шага каждый раз, он может go к второму последнему узлу вместо последнего, и в этом случае проблема не возникает.

Answer 2

Вам нужно проверить свой код (т.е. запустить его в своей голове) на случай:

1 -> 2 -> 3 -|

Это самый простой случай, когда ваш алгоритм ломается.

Ваш код будет установите для a и b значение 1, затем введите l oop. a затем повышается до 2 и b повышается до 3.

В следующей итерации l oop, a повышается до 3, но b остается на 3 потому что b.next равно нулю. Это означает, что a может свободно продвигаться без b, не продвигаясь быстрее или не находя конца. В конце концов, a поймает до b ^(a) , и вы будете считать, что зацикленный список.

То, что вам нужно , чтобы сделать, это продвиньте b на два, если это возможно, но если нет, продвиньте его как можно дальше.

Это так же просто, как (псевдокод):

b = b.next
if b is not null:
    b = b.next

Таким образом, b гарантированно либо опередит a, либо найдет конец списка.

---

Если вам нужны более глубокие знания об этом алгоритме, взгляните на Поиск l oop в односвязном списке , который подробно объясняет оба алгоритма, и , позволяет найти начало l oop.

* 1046. *

^(a) Интересно, что это именно то, что происходит в реальной черепахе и басне. Заяц останавливается, чтобы отдохнуть, и черепаха развевается, в конце концов обгоняя зайца и выигрывая гонку.

Что ж, выиграет гонку, если мы не назовем остановку как как только он догнал: -)