141. Linked List Cycle

주어진 연결 리스트(링크드 리스트)에 순환(사이클)이 존재하는지 여부를 판단하는 문제입니다.

문제 설명:

주어진 연결 리스트에 순환(사이클)이 존재하면 true를, 순환이 존재하지 않으면 false를 반환하세요.

연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 링크로 구성됩니다. 순환(사이클)이 존재한다는 것은 연결 리스트에서 어떤 노드를 시작점으로 하더라도 해당 노드를 지나면 언젠가 다시 동일한 노드에 도달할 수 있다는 것을 의미합니다.

예를 들어, 다음과 같은 연결 리스트가 순환을 가지고 있으면 true를 반환해야 합니다:

3 -> 2 -> 0 -> 4
     ^         |
     |         v
     +---------+

 

반면에, 순환을 가지지 않는 연결 리스트는 다음과 같습니다:

1 -> 2 -> 3 -> 4

순환을 판단하기 위해 해시 테이블을 사용하거나 투 포인터(Two Pointers) 기법을 활용할 수 있습니다. 두 포인터를 사용하여 한 포인터는 한 번에 한 단계씩, 다른 포인터는 한 번에 두 단계씩 이동하게 하고, 만약 순환이 존재하면 두 포인터가 언젠가 만나게 됩니다.

이 문제를 해결하는 가장 일반적인 방법은 투 포인터를 사용하는 것

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

public bool HasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false; // 빈 리스트나 단일 노드는 순환이 없음
    }
    
    ListNode slow = head;
    ListNode fast = head.next;
    
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false; // fast 포인터가 리스트의 끝에 도달하면 순환 없음
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true; // slow와 fast 포인터가 만났으므로 순환 있음
}

투 포인터를 사용하여 연결 리스트에서 순환 여부를 판단하며, 만약 순환이 존재한다면 true를, 그렇지 않으면 false를 반환합니다.