การตรวจจับวัฏจักรด้วยอัลกอริทึมของ Floyd

วงจรในรายการเชื่อมโยงคืออะไร

อัลกอริทึมตัวชี้ช้า-เร็วของฟลอยด์

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]   # cycle: -4 -> 2

print(hasCycle(nodes[0]))  # True

เหตุใดตัวชี้ช้าและเร็วจึงพบกันเสมอ

# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
    gap = start_gap
    steps = 0
    while gap != 0:
        gap = (gap - 1) % cycle_length
        steps += 1
    print(f'Start gap {start_gap}: meet after {steps} step(s)')

การหาจุดเริ่มต้นของวงจร

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1: detect meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    pointer = head
    while pointer is not slow:
        pointer = pointer.next
        slow    = slow.next
    return pointer  # cycle entry node

nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]  # entry is nodes[1] (val=2)

entry = detectCycle(nodes[0])
print(entry.val)  # 2

การพิสูจน์ทางคณิตศาสตร์ของโหนดเริ่มต้น

# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1   # head(3) to entry(2)
C = 3   # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')

การวัดความยาววงจร

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # found meeting point
            length = 1
            fast = fast.next
            while fast is not slow:
                fast = fast.next
                length += 1
            return length
    return 0  # no cycle

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0]))  # 3

จำนวนแฮปปี (ตรวจจับวงจรโดยไม่ใช้รายการ)

def isHappy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow, fast = n, next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(isHappy(19))  # True  (1->81+1=82->68->100->1)
print(isHappy(2))   # False (enters cycle)

การตรวจจับแบบใช้เซตอย่างง่ายเทียบกับวิธีของฟลอยด์

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Naive O(n) space approach
def hasCycle_set(head):
    seen = set()
    while head:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

# Floyd's O(1) space approach
def hasCycle_floyd(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print('Both implementations give the same result')

กรณีขอบสำหรับการตรวจจับวงจร

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Edge cases
print(hasCycle(None))               # False: empty
node = ListNode(1)
print(hasCycle(node))               # False: single, no cycle
node.next = node
print(hasCycle(node))               # True: single node cycle

วงจรในรายการเชื่อมโยง II: LeetCode 142

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    # Phase 2
    ptr = head
    while ptr is not slow:
        ptr  = ptr.next
        slow = slow.next
    return ptr

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val)  # 3

เหตุใดวิธีของฟลอยด์จึงดีกว่าวิธีใช้เซต

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทบทวนบทเรียน