Floyd's Cycle Finding Algorithm (Find a loop in a linked list)

LeetCode의 141번을 풀다가 발견한 알고리즘.

Linked List Cycle - LeetCode

 

설명과 사진은 geeksforgeeks를 참고.

Floyd’s Cycle Finding Algorithm - GeeksforGeeks

 

다른 속도로 움직이는 2개의 포인터를 사용하는 알고리즘이다. 2개의 포인터는 순차적으로 이동한다.

linked list가 순환하는지 확인하기 위해 사용된다. 하나의 포인터는 다른 포인터 보다 2배 빠르게 이동한다.

 

빠르게 움직이는 포인터를 fast pointer

fast pointer 보다 느리게 움직이는 포인터를  slow pointer라고 한다.

 

Fast pointer가 NULL이 된다면 linked list내 loop가 없음을 의미한다.

Fast pointer가 slow pointer를 따라잡게 된다면 linked list내 loop가 존재함을 의미한다.

 

 

LeetCode의 141번 문제. 순환 Linked List면 true, 아니면 false를 반환하면 된다.

/**
     * 내가 제출한 정답 코드
     */
    public boolean hasCycle(ListNode head) {

        Set<Integer> visited = new HashSet<>();
        ListNode currentNode = head;
        while(true) {

            if(currentNode == null || currentNode.next == null) return false;

            if(visited.contains(currentNode.hashCode())) return true;

            visited.add(currentNode.hashCode());
            currentNode = currentNode.next;
        }
    }

    /**
     * 시간복잡도 O(1) 짜리 답안
     * Floyd’s Cycle Finding Algorithm를 공부해볼 것
     * 
     * fast와 slow의 간격을 2가 아닌 1로 함으로써 null 체크 로직을 제거할 수 있었음.
     */
    public boolean hasCycle2(ListNode head) {
        if (head == null) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while(true) {
            if (fast == null) return false;
            if (fast.next == fast) return true;
            slow.next = slow;
            slow = fast;
            fast = fast.next;
        }
    }