A-041● Day 412026.06.16easyleetcode #141neetcode150

연결 리스트 순환 감지

#hash-table#linked-list#two-pointers

문제

· problem

P.041

연결 리스트 순환 감지

연결 리스트의 헤드 노드가 주어졌을 때, 연결 리스트에 순환(사이클)이 있는지 판별하시오. 연결 리스트에서 순환이란 리스트의 어떤 노드에서 시작하여 next 포인터를 따라 계속 이동할 때 다시 도달할 수 있는 노드가 존재하는 경우를 말합니다. 내부적으로 pos는 tail의 next 포인터가 연결된 노드의 인덱스를 나타냅니다. pos는 입력 매개변수로 주어지지 않음을 주의하시오. 연결 리스트에 순환이 있으면 true를 반환하고, 그렇지 않으면 false를 반환하시오.

제약

· 0 ≤ number of nodes ≤ 10^4
· -10^5 ≤ node.val ≤ 10^5
· pos is -1 or a valid index in the linked list

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[3,2,0,-4]
1

true

example 2input → output

[1,2]
0

true

example 3input → output

[1]
-1

false

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
pos 매개변수는 함수 입력으로 주어지는가?
☐
공간 제약이 없다면 해시 테이블을 사용해도 되는가?
☐
연결 리스트가 비어있을 수 있는가?
☐
순환 고리에 진입하기 전에 여러 노드가 있을 수 있는가?
☐
노드를 변경하거나 마킹할 수 있는가?
☐
빠른 포인터가 느린 포인터를 따라잡으면 반드시 순환이 있다는 것이 증명되는가?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 포인터 초기화

○

slow, fast = head, head

○

slow, fast = head, head.next

○

slow = head; fast = None

step 2· 반복 조건 검사

○

while fast and fast.next:

○

while fast:

○

while fast and fast.next and slow:

step 3· 느린 포인터 이동 (1칸)│ 중첩

○

slow = slow.next

○

slow = slow.next.next

○

slow = slow.next if slow else head

step 4· 빠른 포인터 이동 (2칸)│ 중첩

○

fast = fast.next.next

○

fast = fast.next

○

fast = fast.next.next.next

step 5· 포인터 충돌 확인│ 중첩

○

if slow == fast:

○

if slow.val == fast.val:

○

if slow == fast and slow != head:

step 6· 최종 결과 반환

○

return False

○

return True

○

return slow == fast

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def hasCycle(self, head: ListNode) -> bool:

        slow, fast = head, head

        while fast and fast.next:

            slow = slow.next

            fast = fast.next.next

            if slow == fast:

                return True

        return False

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[3,2,0,-4]
1

→

true

case 2

[1,2]
0

→

true

case 3

[1]
-1

→

false

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.