[LeetCode] 141. Linked List Cycle 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Linked List Cycle

---

문제 요약 (Linked List Cycle)

단일 연결 리스트가 주어졌을 때, 해당 리스트에 사이클이 존재하는지 판별하라.
추가 공간 O(1), 리스트 수정 불가

 

문제 링크: https://leetcode.com/problems/linked-list-cycle/

---

🤔 처음 떠올린 아이디어

처음 문제를 봤을 때 이런 생각이 들었다.

같은 노드를 두 번 방문하면 사이클 아닌가?

그러면 자연스럽게 이런 방법이 떠오른다.

Set<ListNode> visited = new HashSet<>();

방문할 때마다 set에 저장하고,
이미 방문한 노드라면 → 사이클.

하지만 문제 조건에 O(1) 공간이 붙는다.

👉 HashSet은 O(n) 👉 사용 불가

그럼 이런 질문이 생긴다.

저장하지 않고, 같은 노드를 다시 방문했는지 알 수 있을까?

---

💡 핵심 깨달음 1: 구조를 다시 보자

정상적인 연결 리스트는 이렇게 생겼다.

• head → A → B → C → null

반드시 끝이 null이다.
그런데 사이클이 있다면?

head → A → B → C → D
               ↑     ↓
               ← ← ← ←

 

즉, 끝이 없다
같은 노드를 다시 방문하게 된다
구조가 “직선”이 아니라 “원형”이다

 

여기서 관점이 바뀌었다.

이건 방문 체크 문제가 아니라,
원형 구조 감지 문제 아닐까?

---

💡 핵심 깨달음 2: 원형 구조에서 벌어지는 일

원형 트랙을 생각해보자.

• A는 1칸씩 이동
• B도 1칸씩 이동

→ 절대 못 만난다 (거리 유지)

그럼 이렇게 바꾸면?

• slow: 1칸
• fast: 2칸

원형이면? 👉 빠른 포인터가 느린 포인터를 따라잡는다.

이 순간이 바로 사이클 존재의 증거다.
여기서 두 포인터 아이디어가 탄생한다.

---

🧠 사고 흐름 정리

1. 한 포인터로는 감지 불가
2. 저장은 못 함 (O(1) 조건)
3. 구조를 보면 원형
4. 원형이면 추격 가능
5. 속도 차이를 만들면 반드시 만난다

즉, 이 문제는 결국 “추격이 일어나는가?”를 보는 문제

---

🔁 Floyd’s Tortoise & Hare

알고리즘 아이디어

• slow → 한 칸
• fast → 두 칸
• 만나면 사이클 존재
• fast가 null 만나면 → 사이클 없음

---

코드 (Java)

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == 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;
    }
}

📐 왜 반드시 만나는가?

사이클 길이를 L이라 하자.

• slow는 1칸
• fast는 2칸

매 스텝마다 거리 차이는 +1

원형에서는 거리 차이가 L이 되는 순간
다시 0이 된다 (mod L)

즉, 반드시 같은 지점에서 만난다.

이건 수학이 아니라
“원형 트랙 추격 직관”이다.


📈 시간/공간 복잡도

• 시간: O(n)
• 공간: O(1)

---

📝 이번 문제에서 얻은 깨달음

• 연결 리스트는 기본적으로 직선 구조
• 사이클은 “원형”이라는 구조적 변화
• 원형 구조에서는 추격이 발생한다
• 두 포인터는 “비교를 만들기 위한 도구”
  
  

👉 결국 중요한 건 “fast/slow를 외웠는가?”가 아니라,
구조가 직선인지 원형인지 먼저 해석했는가