LinkedListCycle
Problem
Solution
Set two pointers, a and b, to head. Move a 1 node at a time but
move b 2 nodes at a time. If a and b ever point to the same node,
then b must have wrapped around the linked list and caught up to a.
Code
from typing import List
class ListNode:
"""Node in a linked list.
"""
def __init__(self, val: int, next: ListNode | None = None):
self.val = val
self.next = next
@classmethod
def from_list(cls, list: List[int]) -> ListNode | None:
head: ListNode | None = None
for el in list:
if head is None:
head = ListNode(el)
node = head
else:
node.next = ListNode(el)
node = node.next
return head
def hasCycle(head: ListNode | None) -> bool:
"""Whether the linked list has a cycle.
"""
if head is None:
return False
a = head
b = head.next
while b is not None:
if a is b:
return True
a = a.next
b = b.next
if b is not None:
b = b.next
return False
Test
>>> from LinkedListCycle import ListNode, hasCycle
>>> head = ListNode.from_list([3, 2, 0, -4])
>>> head.next.next.next.next = head.next
>>> hasCycle(head)
True
>>> head = ListNode.from_list([1, 2])
>>> head.next.next = head
>>> hasCycle(head)
True
>>> head = ListNode.from_list([1])
>>> hasCycle(head)
False