Follow

Follow

·Jun 10, 2022·

# 簡介 Intro

## 解釋

### 進階題目

#### 找出迴圈長度

``````def detectCycle(self):
# then no loop

if not (temp):
return False
tortoise = temp
hare = temp.next
power = 1
length = 1

# This loop runs till we
# find the loop. If there
# is no loop then second
# pointer ends at NULL
while hare and hare != tortoise:

# condition after which
# we will update the power
# and length as smallest
# power of two gives
# the start of cycle.
if length == power:

# updating the power.
power *= 2

# updating the length
length = 0

tortoise = hare

hare = hare.next
length += 1
# if it is null then no loop
if not (hare):
return
``````

#### 找出迴圈連結點

``````A + B = C
A = C - L
C - L + B = C
C - C + B = L
B = L
``````

``````
# Now set tortoise pointer
# to the beginning and
# hare pointer to
# beginning plus cycle
# length which is length.
while length > 0:
hare = hare.next
length = length - 1

# Now move both pointers
# at same speed so that
# they meet at the
# beginning of loop.
while hare != tortoise:
hare = hare.next
tortoise = tortoise.next