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 pointerhare). - 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.
Inputs
Arg 1:
[1,2,3]Arg 2:
-1Expected Output
falseActual Output