Ch.5 연결 리스트
Fast & Slow 포인터 — 토끼와 거북이
빠른 토끼와 느린 거북이가 만난다?
두 포인터가 같은 출발점에서 시작합니다. slow는 1칸, fast는 2칸씩 이동합니다. fast가 끝에 도달하면 slow는 정확히 중간에 있습니다.
만약 리스트에 사이클(순환)이 있다면?
사이클이 있으면 fast가 slow를 반드시 따라잡습니다. 이것이 Floyd's Cycle Detection입니다.
핵심 개념
Fast 포인터
한 번에 2칸씩 이동하는 포인터
Slow 포인터
한 번에 1칸씩 이동하는 포인터
핵심 내용
리스트의 중간 노드를 찾으려면 길이를 모를 때 어떻게 할까요?
def find_middle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next # 1칸
fast = fast.next.next # 2칸
return slow # 중간 노드fast가 2배 빠르므로, fast가 끝에 도달할 때 slow는 정확히 절반 위치입니다
리스트에 사이클이 있으면 fast가 끝에 도달하지 못합니다
사이클이 있으면 fast와 slow는 반드시 만납니다 (원형 트랙에서 빠른 러너가 느린 러너를 따라잡듯)
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 만남!
return True
return False # fast가 끝에 도달 → 사이클 없음Floyd's 알고리즘 핵심 사이클 있음: slow와 fast가 반드시 만남 → True 사이클 없음: fast가 None에 도달 → False 시간 O(n), 공간 O(1)
사이클이 있다면 어디서 시작하는지도 찾을 수 있습니다
def detect_cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 만남 지점
break
else:
return None # 사이클 없음
# 시작점 찾기: head와 만남점에서 동시 출발
slow = head
while slow != fast:
slow = slow.next
fast = fast.next # 이번엔 둘 다 1칸씩
return slow # 사이클 시작점수학적 증명: 만남점에서 head까지 거리 = 만남점에서 사이클 시작점까지 거리
Fast & Slow로 중간을 찾고 뒷부분을 Reverse하면 Palindrome을 판별합니다
def is_palindrome(head):
# 1단계: 중간 찾기 (Fast & Slow)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2단계: 뒷부분 뒤집기
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
# 3단계: 앞뒤 비교
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return TrueFast & Slow + Reverse 조합은 면접에서 자주 등장합니다. 두 패턴을 합치는 연습이 중요!
Fast & Slow 활용 총정리 중간 노드: fast가 끝 → slow가 중간 사이클 탐지: slow == fast → 사이클 사이클 시작점: 만남점 + head 동시 이동 Palindrome: 중간 찾기 + 뒤집기 + 비교
길이 7인 리스트에서 slow/fast로 중간 노드를 찾으면 몇 번째 노드인가?
사이클이 없는 리스트에서 has_cycle을 호출하면 무한 루프가 발생한다
Floyd's 알고리즘의 공간 복잡도: O(___)
Palindrome 판별에서 Fast & Slow로 중간을 찾은 뒤, 어떤 연산을 하는가?
Fast & Slow 마스터!
핵심 용어
Fast 포인터
한 번에 2칸씩 이동
Slow 포인터
한 번에 1칸씩 이동
정리 노트
Fast & Slow — 토끼와 거북이
활용 패턴
- 중간 노드
- fast가 끝 → slow가 중간
- 사이클 탐지
- slow == fast → 사이클 있음
- 사이클 시작점
- 만남점 + head에서 동시 1칸씩 → 시작점에서 만남
복잡도
- 시간
- O(n)
- 공간
- O(1) — 포인터 2개
Fast & Slow는 '리스트 절반' + '사이클' 문제의 만능 도구!
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작