Floyd's Cycle Detection

플로이드의 순환 감지 알고리즘: 연결 리스트 순환을 찾는 가장 효율적인 방법

문제 상황 및 해결 방법

연결 리스트(LinkedList)에서 순횐(cycle)이란, 연결 리스트가 자기 자신으로부터 루프백되는 것을 의미하며, 반드시 리스트의 시작점으로 돌아가는 것은 아닙니다.

첫 번째 접근법: 노드 마킹

// 각 노드를 방문할 때 마킹하는 방법
public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    
    while (head != null) {
        if (visited.contains(head)) {
            return true;  // 이미 방문한 노드 발견
        }
        visited.add(head);
        head = head.next;
    }
    
    return false;
}

문제점:

• 공간 복잡도 O(n): 모든 노드를 저장해야 함

• 연결 리스트 수정 불가능한 경우 사용할 수 없음

플로이드 알고리즘

핵심 아이디어: 서로 다른 속도로 움직이는 두 개의 포인터 사용

• slow 포인터: 1칸씩 이동

• fast 포인터: 2칸씩 이동

example. 레이스 트랙

연결 리스트를 레이스트랙이라고 생각해보세요. 두 대의 자동차가 서로 다른 속도로 트랙을 달리고 있습니다.

레이스트랙에 루프가 있는 경우:
═══════════╗
           ║
    🚗     ║  🏎️ (빠른 차)
  (느린 차) ║
           ║
═══════════╝

시간이 지나면...
═══════════╗
           ║
           ║  
     🚗🏎️  ║  (충돌!)
           ║
═══════════╝

핵심 원리:

1. 루프가 있다면: 빠른 차가 결국 느린 차를 따라잡아 충돌

2. 루프가 없다면: 빠른 차가 먼저 트랙 끝에 도달

구현 및 주의사항

❌ 잘못된 구현

public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public boolean hasCycle(ListNode head) {
    // null 체크
    if (head == null) {
        return false;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && slow != null) {
        if (fast == slow) {  // ❌ 문제: 처음부터 같음!
            return true;
        }
        fast = fast.next.next;  // ❌ 문제: NullPointerException 가능!
        slow = slow.next;
    }
    
    return false;
}

문제점:

1. 초기 위치 문제: fast와 slow가 모두 head에서 시작하면 첫 번째 비교에서 바로 true 반환

2. Null Pointer Exception: fast.next.next에서 fast.next가 null일 수 있음

✅ 올바른 구현

public boolean hasCycle(ListNode head) {
    // null 체크
    if (head == null) {
        return false;
    }
    
    // 시작 위치를 다르게 설정
    ListNode slow = head;           // 첫 번째 노드에서 시작
    ListNode fast = head.next;      // 두 번째 노드에서 시작
    
    // null 체크 조건 강화
    while (fast != null && fast.next != null && slow != null) {
        if (fast == slow) {  // 충돌 감지
            return true;
        }
        
        // 안전한 이동
        fast = fast.next.next;  // 2칸 이동
        slow = slow.next;       // 1칸 이동
    }
    
    return false;  // 끝에 도달 = 순환 없음
}

1. 서로 다른 시작 위치

• 처음부터 같은 위치에 있지 않도록 함

• 첫 번째 루프에서 바로 true가 반환되는 것을 방지

1. null 체크

• fast != null: fast 자체가 null이 아님을 확인

• fast.next != null: fast.next.next 접근 전에 안전성 보장

• slow != null: 완전성을 위한 체크 (실제로는 불필요할 수 있음)

• 이로 인해 안전한 포인터 이동이 가능합니다.

활용

1. 순환 존재 여부 확인

public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return false;
    }

2. 순환 시작점 찾기

public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        
        // 1단계: 순환 감지
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                // 2단계: 시작점 찾기
                slow = head;  // slow를 처음으로 되돌림
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;  // 이제 fast도 1칸씩만
                }
                return slow;  // 순환 시작점
            }
        }
        
        return null;  // 순환 없음
    }

3. 순환의 길이 구하기

public int getCycleLength(ListNode head) {
        ListNode cycleStart = detectCycle(head);
        if (cycleStart == null) {
            return 0;
        }
        
        int length = 1;
        ListNode current = cycleStart.next;
        while (current != cycleStart) {
            current = current.next;
            length++;
        }
        
        return length;
    }

시간/공간 복잡도

시간 복잡도: O(n)

• 순환이 없는 경우: 토끼가 끝까지 가므로 O(n)

• 순환이 있는 경우: 최악의 경우 토끼가 순환을 한 바퀴 돌기 전에 만남

공간 복잡도: O(1)

• 추가 자료구조 없이 두 개의 포인터만 사용

• 입력 크기와 무관하게 일정한 메모리 사용

응용

1. 각 자리 제곱 수의 합이 1이 되거나 순환

public boolean isCycle(int n) {
    if (n == 1) return true;
    
    int slow = n;
    int fast = getNext(n);  // 한 칸 앞서 시작
    
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    
    return fast == 1;
}

private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

2. 배열에서 중복 찾기: 배열의 값을 인덱스로 사용하여 순환 감지

public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];  // fast를 한 칸 앞서 시작
    
    // 순환 감지
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    
    // 순환 시작점 찾기
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
}

기본 문제

• LeetCode 141: Linked List Cycle

• LeetCode 142: Linked List Cycle II

응용 문제

• LeetCode 202: Happy Number

• LeetCode 287: Find the Duplicate Number

• LeetCode 457: Circular Array Loop