This code solves the Linked List Cycle problem. If the hare (a pointer) starts ahead of the turtle (also a pointer) and the hare ends up passing the turtle from behind, then we know there must have been a cycle in the race course (the linked list). This is a Two-Pointer problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | # 141. Linked List Cycle
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
hare = head.next
turtle = head
while hare and hare.next:
if hare.next == turtle or turtle == hare:
return True
else:
turtle = turtle.next
hare = hare.next.next
return False
|
Like this post? Share on:
Twitter
❄ Facebook
❄ Email