[알고리즘] LeetCode - Linked List Cycle

Linked List Cycle - LeetCode

문제 설명

• LinkedList의 head가 주어진다.
• 해당 LinkedList의 Cycle을 가지고 있는지 판단하고 결과값을 반환한다.
• 순환이 있으면 true, 없으면 false를 반환해야 한다.

문제 해결

• 플로이드 사이클 검출 알고리즘을 이용해 문제를 해결했다.
• 2개의 포인트를 사용해 1개는 한 칸씩, 또 다른 1개는 두 칸씩 이동시켜 null이 될 때(마지막에 도착할 때)까지 반복한다.
• Cycle이 존재하는 경우 while문 안에서 계속 순회하기 때문에 언젠간 두 포인터가 만난다.
• Cycle이 존재하지 않는 경우 두 칸씩 이동하는 포인터가 먼저 null이 된다.
• 두 포인터의 값을 비교하여 두 칸씩 이동하는 포인터가 먼저 null이 되는 경우 Cycle이 존재하지 않는 경우이고, 두 개의 포인터의 값이 같아지는 경우에는 Cycle이 존재하는 경우로 판단한다.

시간 복잡도

• O(N)

풀이 코드

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}

결과

시간	메모리
0 ms	43.5 MB

---

플로이드 사이클 검출 알고리즘이란?

Linked List에 순환(Cycle)이 있는지 확인하는 문제를 해결하는 토끼와 거북이 알고리즘으로 알려진 알고리즘이다.

알고리즘 원리

1. 빠른 포인터(fast)와 느린 포인터(slow) 두 개의 포인터를 사용한다. 

2. fast는 한 번에 두 개의 노드를 건너뛰고, slow는 한 번에 하나의 노드만을 건너뛰는 방식으로 움직인다.

3. 순환(Cycle) 여부를 판단한다.

- 순환이 있는 경우 : fast는 slow보다 먼저 끝에 도달하게 된다. (fast가 먼저 null이 된다.)

- 순환이 없는 경우 : fast와 slow는 같은 반복문안에서 돌아가기 때문에 언젠간 만나게 된다. (fast와 slow값이 같아진다.)