문제 링크
문제 설명
단일 연결 리스트의 head가 주어졌을 때, 이 리스트에 사이클이 있는지 여부를 확인하는 함수를 작성하세요.
- 사이클의 정의: 사이클이 존재한다는 것은, 리스트의 어떤 노드에서
next포인터를 따라 이동할 때 다시 그 노드로 돌아올 수 있는 구조를 의미합니다.pos는 연결 리스트의 마지막 노드가 가리키는 위치를 나타내며, 실제로 함수의 매개변수로 제공되지는 않습니다. - 출력: 사이클이 있으면
true를, 없으면false를 반환합니다.
예제
- 예제 1
- 입력:
head = [3,2,0,-4],pos = 1 - 출력:
true - 설명: 리스트에 사이클이 존재하며,
tail노드가1번째 노드에 연결되어 있습니다.
- 입력:
- 예제 2
- 입력:
head = [1,2],pos = 0 - 출력:
true - 설명: 리스트에 사이클이 존재하며,
tail노드가0번째 노드에 연결되어 있습니다.
- 입력:
- 예제 3
- 입력:
head = [1],pos = -1 - 출력:
false - 설명: 리스트에 사이클이 없습니다.
- 입력:
풀이 전략
연결 리스트에 사이클이 있는지 확인하기 위해서는, 리스트를 순회하면서 노드를 재방문할 수 있는지를 확인해야 합니다.
- 투 포인터 (Floyd의 Cycle Detection 또는 "토끼와 거북이" 알고리즘):
- 두 개의 포인터
slow와fast를 사용합니다.slow는 한 번에 한 노드씩 이동하고,fast는 한 번에 두 노드씩 이동합니다. - 리스트에 사이클이 있다면,
fast포인터가 사이클을 돌아서slow포인터와 만나게 됩니다. - 리스트에 사이클이 없다면,
fast포인터가 리스트의 끝에 도달하게 되어 사이클이 없음을 확인할 수 있습니다.
- 두 개의 포인터
- 시간 및 공간 복잡도:
- 시간 복잡도: (O(n)) - 리스트의 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: (O(1)) - 추가 메모리를 거의 사용하지 않습니다.
코드 분석
투 포인터 (Floyd의 Cycle Detection)
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None:
return False
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next # slow 포인터는 한 칸씩 이동
fast = fast.next.next # fast 포인터는 두 칸씩 이동
if slow == fast: # 두 포인터가 만나면 사이클 존재
return True
return False # fast가 끝에 도달하면 사이클이 없음- 동작 원리:
slow와fast두 포인터를 초기화합니다.while루프에서fast가 리스트의 끝에 도달하지 않을 때까지 두 포인터를 각각 한 칸, 두 칸씩 이동합니다.slow와fast가 동일한 노드를 가리키면 사이클이 존재하므로True를 반환합니다.- 루프가 종료되면
fast가None에 도달하여 리스트의 끝에 도달한 것이므로False를 반환합니다.
- 시간 복잡도: (O(n)) - 리스트의 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: (O(1)) - 두 포인터만 사용하여 메모리 사용을 최소화합니다.
요약
- 이 문제는 Floyd의 Cycle Detection 알고리즘을 사용하여 해결할 수 있습니다.
- 두 포인터(
slow,fast)를 사용하여 리스트 내 사이클을 효율적으로 탐지할 수 있습니다. - 시간 복잡도 (O(n)), 공간 복잡도 (O(1))으로 매우 효율적인 풀이입니다.