141. Linked List Cycle

 

📌 Problem Link :

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

✅ Accepted :

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;

        ListNode current = head;

        while (current.next != null) {
            if (current.val == 100001) return true;
            current.val = 100001;
            current = current.next;
        }
        return false;
    }
}

 

🧐 Review :

리트코드 141번 문제는 주어진 연결 리스트(Linked List) 내에 순환(Cycle)이 존재하는지 판별하는 문제입니다.

 

1. 첫 번째 접근 방식 :

처음에는 연결 리스트를 순회하며 각 노드의 val을 문제에서 정한 범위를 벗어나는 임의의 값으로 업데이트하는 방식을 생각했습니다.
순회 중 이미 업데이트된 값을 가진 노드를 다시 만난다면, 해당 리스트에 순환이 존재한다고 판별하는 로직이었습니다.

 

2. 피드백 및 개선 :

하지만 코드 리뷰를 통해 원본 데이터(노드의 값)를 직접 수정하는 방식은 문제의 의도에서 벗어날 수 있다는 점을 알게 되었습니다. 실제 실무 환경에서도 읽기 전용 데이터일 경우 이 방식은 적용하기 어렵기 때문입니다.

 

3. 최종 풀이:

이를 보완하기 위해 'Floyd’s Cycle Detection(플로이드의 순환 탐색)' 알고리즘을 도입했습니다.

이 알고리즘의 핵심은 속도가 다른 두 개의 포인터를 사용하는 것입니다. 

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        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;
    }
}

 

• slow 포인터: 한 번에 한 칸씩 이동합니다.
• fast 포인터: 한 번에 두 칸씩 이동합니다.

만약 리스트에 순환이 존재한다면, 속도가 빠른 fast 포인터가 어느 시점에는 반드시 slow 포인터를 뒤따라 잡게 됩니다.

즉, 두 포인터가 동일한 노드에서 만나는 순간 순환이 있음을 확신할 수 있습니다. 반면, 리스트의 끝(null)에 도달하면 순환이 없는 것으로 판단합니다.