Linked List Cycle Detection

Advanced

Let's go on a detective adventure in the world of linked lists!

In computer science, a linked list is a linear collection of data elements where each element points to the next one, forming a sequence. Now imagine that during this sequence, one of these elements decides to point backwards instead. This creates a cycle!

Your task is to write a function, has_cycle, that will detect if there is a cycle in a linked list.

A linked list node is defined below:

class ListNode: def __init__(self, x): self.val = x self.next = None

Examples

Let's see some examples of how has_cycle works:

Example 1: No Cycle

# Linked list: 1 -> 2 -> 3 -> None node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node1.next = node2 node2.next = node3 print(has_cycle(node1)) # Output: False

Example 2: Contains a Cycle

# Linked list: 1 -> 2 -> 3 -> 2 (cycle back to node2) node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node1.next = node2 node2.next = node3 node3.next = node2 # Creates a cycle print(has_cycle(node1)) # Output: True

Hints:

  • You can use two pointers at different speeds to solve this problem, a common technique known as the "Tortoise and the Hare".
  • One pointer moves one step at a time (slow pointer tortoise), and the other moves two steps at a time (fast pointer hare).
  • If the linked list has a cycle, these two pointers will eventually meet at the same node (like how a faster hare on a circular track will eventually catch up to a slower tortoise).

How the tests work

Each test gives the list's values and the position (counting from 0) that the last node links back to, or -1 when there is no cycle. The list is built for you, so [1, 2, 3] with position 1 is Example 2.

Geek
Inputs

Arg 1:

[1,2,3]

Arg 2:

-1
Expected Output
false
Actual Output