[파이썬] Floyd's Cycle Detection 알고리즘

링크드 리스트에서 사이클(순환)을 찾는 알고리즘 중에 Floyd's Cycle Detection Algorithm (플로이드 순환 찾기 알고리즘)이 있습니다. 두 포인터를 이용해서 첫 번째 포인터는 one step 이동(slow pointer) 두 번째 포인터는 two step 이동하면서(fast pointer) 두 포인터가 만나게 된다면 리스트는 순환 사이클이 존재하는 것입니다.

 

 

싸이클 존재

Floyd's Cycle Detection 알고리즘 예제 코드

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


def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        # move step one
        slow = slow.next
        # move step two
        fast = fast.next.next

        # they met
        if slow == fast:
            return True
    return False


if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)
    node6 = ListNode(6)

    # node1 -> node2 -> node3 -> node4 -> node5 -> node6 -> node3 -> ...
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node6

    # cycle
    node6.next = node3

    head = node1
    assert has_cycle(head)

 

함께 보면 좋은 글:

https://leetcode.com/problems/linked-list-cycle/

Linked List Cycle - LeetCode