Does the Linked List have a cycle?

Question

I'm stuck on the following leetcode problem.

Given a singly linked list determine if there exists a cycle. If so, return True. Otherwise, return False.

My reasoning: Allow for two pointers to go through the entire single linked list. One of the pointers move one node at a time while the other pointer will touch every other node. If there exists a cycle the pointers will eventually meet.

Here is my attempt (in 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

I submitted this code to leetcode and I was able to pass all the test cases except the really long one.

However, the following code works fine (written by someone else):

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

To me, the main difference is the while statement's condition. However, I still don't see the error in my code.

Comparisons with None should be done using `is None`, not `== None`. — AMC, Jan 18 '20 at 01:38

score 4 · Accepted Answer · answered Jan 18 '20 at 01:37

There are two other differences between these two solutions. The first one is trivial; your solution initialises currB = head, whereas the other solution's fast variable is initialised as head.next. This should have almost no impact on the working of the algorithm.

The difference that matters is that your solution leaves currB unchanged when currB.next is None. The other solution terminates in that case by returning False, but yours will sit there with currB at the last node, unchanged, while currA steps along towards the end of the list. Eventually, currA reaches the last node, and at that point currA and currB are equal; so your algorithm thinks it has detected a cycle, but really it's because your currB pointer stopped moving forwards and the other one caught up with it.

This problem doesn't occur for every non-cyclic list; only when currB ends up as the last node. This depends on the parity of the length of the list, since currB advances two steps each time, it may go to the second-last node instead of the last one, in which case the problem doesn't occur.

Ironically, this algorithm is sometimes called the "hare and tortoise" algorithm because of how one pointer traverses the list faster than the other; and just like Aesop's story, your hare goes to sleep and the tortoise catches it! — kaya3, Jan 18 '20 at 01:42

paxdiablo · Answer 2 · 2020-01-18T01:56:58.900

You need to examine your code (i.e., run it in your head) for the case of:

1 -> 2 -> 3 -|

That's the simplest case where your algorithm breaks.

Your code will set both a and b to point to 1 then enter the loop. a then advances to 2 and b advances to 3.

In the next loop iteration, a advances to 3 but b stays at 3 because b.next is null. This means that a is free to advance without b either advancing faster or finding the end. Eventually, a will catch up to b^(a) and you will consider that a looped list.

What you need to do instead is is advance b by two if possible but, if not, advance it as far as you can.

This is as simple as (pseudo-code):

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

That way, b is guaranteed to either keep ahead of a or find the list end.

If you're interested in more in-depth knowledge on this algorithm, have a look at Finding loop in a singly linked-list, which explains both the algorithm itself in detail, and provides a way to find the start of the loop.

^(a) Interestingly, this is exactly what happens in the actual tortoise and hare fable. The hare stops to take a rest and the tortoise plods along, eventually passing the hare and winning the race.

Well, it would win the race if we didn't call a stop as soon as it caught up :-)

Does the Linked List have a cycle?

2 Answers2