Linked List Cycle Detection

Problem

Detect whether a singly linked list contains a cycle using Floyd's tortoise and hare algorithm.

values gives the node values in order and pos is the index the tail links back to, or -1 when there is no cycle. Advance a slow pointer one step and a fast pointer two steps; if they ever meet, a cycle exists.

Return True if a cycle exists, otherwise False.

Hint

If there is no cycle the fast pointer reaches the end; if there is one it laps the slow pointer.

Test cases

case 1

in: [[3,2,0,-4],1]

expected: true

case 2

in: [[1,2],0]

expected: true

case 3

in: [[1],-1]

expected: false

case 4

in: [[],-1]

expected: false

case 5

in: [[1,2,3],-1]

expected: false

Starter codePython

def has_cycle(values, pos):
    # Your code here
    pass

5 test cases · run your code against them in the editor