ListNode(val, next=None) is in the starter. Keep it.
Normally a linked list ends: follow next from head long enough and you reach None. A broken list can instead loop, with the last node's next pointing back at a node you've already passed, so the walk goes round forever. Write has_cycle(head) -> bool that returns True if the list loops and False if it ends.
3 -> 7 -> 2 -> 9 -> (back to 7) True
4 -> 4 -> 1 -> None False (repeated values are fine; the list still ends)
5 -> (back to 5) True (a single node pointing at itself)
None False (an empty list)
Values may repeat, so compare nodes, not values. Don't modify the list. The list has up to 100,000 nodes. A set of visited nodes passes, but try to use O(1) extra memory.
⭐ Bonus: a speed test with 100,000-node lists earns a star in O(n) time.
Show hint
Send two pointers down the list, one moving one step at a time and the other two. If the list ends, the fast one finds None. If it loops, what happens to the gap between them once both are going round?