LeetCode #141 Linked List Cycle: เต่ากับกระต่ายพิสูจน์วงโดยไม่ใช้แรมเพิ่ม

โจทย์ถามว่า linked list มีโหนดใดชี้ย้อนกลับจนเกิดวงหรือไม่ ไม่ต้องหาจุดเริ่มวงครับ ความยากคือห้ามเดินจน None อย่างเดียว เพราะถ้ามีวงลูปจะไม่จบ

วิธีที่ 1: Hash set ของโหนดที่เคยเห็น

เดินทีละโหนด หาก object เดิมอยู่ใน set แล้วแปลว่ากลับมาจุดเดิม เวลา O(n), หน่วยความจำ O(n) อ่านง่ายและดัดแปลงเพื่อหาจำนวนโหนดก่อนวนได้สะดวก ต้องเก็บ identity ของ node ไม่ใช่ค่า เพราะหลายโหนดมีค่าเท่ากันได้

วิธีที่ 2: Floyd slow/fast — ค่าเริ่มต้นที่แนะนำ

ให้ slow ขยับหนึ่งก้าวและ fast สองก้าว หากไม่มีวง fast จะถึง None หากมีวง เมื่อทั้งคู่เข้าวง ระยะห่างบนวงจะลดลงหนึ่งตำแหน่งต่อรอบจนพบกัน เวลา O(n), พื้นที่ O(1) และไม่แก้ input

import unittest


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


def has_cycle_set(head):
    seen = set()
    while head:
        if head in seen:
            return True
        seen.add(head)
        head = head.next
    return False


def has_cycle_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


def build(values, cycle_at=None):
    nodes = [ListNode(value) for value in values]
    for left, right in zip(nodes, nodes[1:]):
        left.next = right
    if nodes and cycle_at is not None:
        nodes[-1].next = nodes[cycle_at]
    return nodes[0] if nodes else None


class LinkedListCycleTests(unittest.TestCase):
    def test_cycle_and_non_cycle(self):
        for head, expected in ((build([], None), False), (build([1], None), False),
                               (build([1], 0), True), (build([3, 2, 0, -4], 1), True)):
            self.assertEqual(has_cycle_set(head), expected)
            self.assertEqual(has_cycle_floyd(head), expected)


if __name__ == "__main__":
    unittest.main()

เลือกตามสถานการณ์

เงื่อนไข	Hash set	Floyd
input ใหญ่	O(n) heap อาจแพง	O(1) เพิ่ม เหมาะกว่า
memory จำกัด	ไม่เหมาะ	ดีที่สุด
readability/debug	ตรงไปตรงมาและ inspect ได้	ต้องเข้าใจ invariant
sorted/streaming	ค่าเรียงไม่ช่วย; stream ที่ย้อน identity ไม่ได้ใช้ไม่ได้	ต้องมี pointer ที่เดินซ้ำได้
อนุญาตแก้ input	ไม่แก้	ไม่แก้

best default คือ Floyd เพราะตรง constraints และใช้พื้นที่คงที่ แต่ใน production debugging hash set อาจอธิบายเส้นทางได้ง่ายกว่า

Edge cases และหลุมพราง

ลิสต์ว่าง, โหนดเดียวไม่วน, โหนดเดียวชี้ตัวเอง, วงเริ่มที่หัว และหางยาวก่อนเข้าวงต้องผ่าน อย่าเทียบ slow.val == fast.val; ต้องใช้ identity is เพราะค่าซ้ำไม่ใช่วง และใน loop condition ต้องตรวจ fast.next ก่อนขยับสองก้าว

Recap

• set จำ identity และใช้พื้นที่ O(n)
• Floyd ใช้ความเร็ว 1 ต่อ 2 และพื้นที่ O(1)
• ค่าในโหนดซ้ำกันไม่ใช่หลักฐานของ cycle
• default เลือก Floyd เมื่อโจทย์ถามเพียง true/false