Linked List Cycle

Q: 연결 리스트 사이클의 시간 및 공간 복잡도는 어떻게 되나요?

두 접근 방식 모두 모든 노드를 제한된 횟수만큼 방문하므로 O(n) 시간이 걸립니다. 방문한 노드를 표시하려면 O(n) 의 추가 메모리가 필요합니다. Floyd의 빠른 포인터와 느린 포인터는 노드 번호 두 개만 사용하므로 O(1) 이 필요합니다.

Q: 빠른 포인터가 느린 포인터를 건너뛸 수 없는 이유는 무엇인가요?

사이클 내부에서는 각 라운드마다 fast 는 노드 두 개를 이동하고 slow 는 한 개를 이동하므로, fast 가 slow 에 도달하기 위해 이동해야 하는 거리는 정확히 1씩 줄어듭니다. 라운드마다 1씩 줄어드는 거리는 3, 2, 1, 0이 되며 0을 지나칠 수 없으므로 두 포인터는 한 노드에서 만납니다.

Q: 단계를 세어 순환을 감지할 수 있나요?

이 배열 형태에서는 그렇습니다. 순환이 없는 리스트는 n 번의 링크 이동 안에 -1 에 도달하므로, 끝에 도달하지 않고 n 번의 링크를 이동하면 순환이 있다는 것을 증명할 수 있으며, 메모리는 O(1) 만 사용합니다. 이 방법은 노드의 개수가 필요한데, 포인터로 이루어진 리스트에서는 노드의 개수를 알 수 없고, 순환이 있으면 먼저 노드 수를 세는 작업이 끝나지 않습니다. Floyd의 방법에는 개수를 셀 필요가 없습니다.

쉬움빠른 포인터와 느린 포인터 연결 리스트

+10

연결 리스트는 배열 next에 저장됩니다. 노드 i는 노드 next[i]에 연결되고, -1은 그 지점에서 리스트가 끝난다는 뜻입니다. 헤드는 노드 0입니다. 헤드에서 연결을 따라가면서 이미 방문한 노드로 다시 돌아오면 true를 반환하고, 끝에 도달하면 false를 반환하세요. 따라가는 과정에서 도달하지 못하는 노드들은 서로 루프를 이루며 연결되어 있더라도 포함하지 않습니다.

함수

hasCycle(next: integer-array) → boolean

nextinteger-array: 모든 노드의 링크: next[i]는 노드 i 다음에 오는 노드이거나 -1입니다
반환값boolean: 노드 0에서 시작한 이동이 노드를 다시 방문하면 true, -1에 도달하면 false

제약 조건

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
여러 노드가 같은 노드를 가리킬 수 있으며, 일부 노드는 헤드에서 도달할 수 없을 수도 있습니다.

예제

입력: next = [1, 2, 3, 1]
출력: true
설명: 순회는 0, 1, 2, 3으로 진행한 다음 다시 1로 돌아갑니다. 노드 1은 두 번 방문되므로 목록에는 노드 1, 2, 3을 거치는 사이클이 있습니다.

입력: next = [2, -1, 1]
출력: false
설명: 이동은 0, 2, 1로 이어진 다음 -1에 도달합니다. 서로 다른 노드 3개를 거친 다음 끝에 도달하므로 사이클이 없습니다.

입력: next = [-1, 2, 1]
출력: false
설명: 노드 0은 -1에 연결되어 있으므로 목록의 길이는 노드 하나입니다. 노드 1과 2는 서로 연결되어 루프를 이루지만, 헤드에서 시작하는 순회는 이 노드들에 도달하지 않습니다.

제출 시 숨은 테스트 +16개

후속 질문

추가 메모리 O(1)만 사용하면서 사이클이 시작되는 노드도 찾을 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

사이클이 없는 리스트는 n개의 링크를 따라가면 -1에 도달하지만, 사이클이 있는 리스트는 끝나지 않으므로 끝을 기다릴 수 없습니다. 이동이 빙빙 돌고 있다는 것을 알아차릴 방법이 필요합니다. 방문하는 모든 노드를 기억하면 O(n)의 메모리가 필요합니다. Floyd의 빠른 포인터와 느린 포인터를 사용하면 정수 두 개만으로 이를 해결할 수 있습니다. 루프 안에서는 두 배 빠르게 움직이는 포인터가 느린 포인터를 따라잡기 때문입니다.

방문한 노드에 표시하기

핵심 아이디어

노드 0에서 시작해 각 노드를 떠날 때 표시하세요. 이미 표시된 노드에 도달하면 이전에 방문한 노드로 돌아온 것이며, 그 지점부터 계속 반복됩니다. 이것이 사이클입니다. 예제 1에서는 0, 1, 2, 3을 표시하고, 노드 3에서 이어지는 링크가 이미 표시된 노드 1로 연결됩니다.

노드 번호는 0부터 n-1까지이므로 길이가 n인 불리언 배열을 방문한 노드의 집합으로 사용할 수 있습니다. 객체로 연결 리스트를 만들었다면 대신 노드 참조를 해시 집합에 넣으면 됩니다. 기본 아이디어는 같습니다.

각 노드는 최대 한 번만 표시되고, 처음으로 반복되는 노드에 도달하거나 -1에 도달하면 탐색이 멈추므로 최대 n단계가 걸립니다. 즉, 시간은 O(n)이고 표시를 저장하는 메모리는 O(n)입니다.

알고리즘

모두 false인 길이 n의 불리언 배열 visited를 만듭니다.
node = 0으로 설정합니다.
node가 -1이 아닌 동안 visited[node]가 이미 true이면 true를 반환합니다.
그렇지 않으면 visited[node]를 설정하고 next[node]로 이동합니다.
탐색이 -1에 도달하면 false를 반환합니다.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

빠른 포인터와 느린 포인터(Floyd의 사이클 탐지)

핵심 아이디어

두 포인터를 헤드에서 시작합니다. slow는 매 라운드마다 링크 하나를 따라가고 fast는 두 개를 따라갑니다. 리스트가 끝나면 fast가 먼저 -1에 도달하고 false를 반환합니다. 사이클이 있으면 fast가 먼저 사이클에 들어가 계속 돌다가 slow도 도착합니다.

두 포인터가 모두 사이클 안에 들어간 후에는 매 라운드마다 fast가 slow보다 정확히 노드 하나씩 앞서갑니다. fast가 slow에 도달하기까지 이동해야 하는 거리는 매 라운드마다 하나씩 줄어들므로, 결국 0이 되어 두 포인터가 같은 노드에 도달합니다. 한 번에 노드 하나씩 앞서가므로 fast는 slow를 절대 뛰어넘을 수 없습니다.

예제 1에서 한 라운드가 지난 후 slow는 노드 1에, fast는 노드 2에 있습니다. 두 라운드가 지난 후 slow는 노드 2에 있고 fast는 3, 1을 거쳤습니다. 세 라운드가 지난 후 둘 다 노드 3에 있으므로 답은 true입니다.

slow가 사이클에 들어가는 데는 최대 n라운드가 필요하고, 사이클 안에 들어간 후에는 한 바퀴를 다 돌기 전에 두 포인터가 만나므로 시간 복잡도는 O(n)입니다. 필요한 메모리는 노드 번호 두 개뿐입니다.

알고리즘

slow = 0과 fast = 0으로 설정합니다.
fast가 -1이 아니고 next[fast]가 -1이 아닌 동안, slow는 링크 하나만큼 이동시키고 fast는 링크 두 개만큼 이동시킵니다.
이동할 때마다 두 포인터가 같은 노드에 있으면 true를 반환합니다.
루프가 끝나면 fast가 끝에 도달한 것이므로 false를 반환합니다.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

함정과 경계 사례

여기서 주의할 점은 목록의 끝과 어떤 노드가 포함되는지에 관한 것입니다.

두 링크를 모두 확인하지 않고 fast를 이동하는 경우입니다. next[next[fast]]를 읽기 전에 fast와 next[fast]가 모두 실제 노드여야 합니다. 그렇지 않으면 next[-1]을 읽게 되며, 대부분의 언어에서는 오류가 발생하고 Python에서는 조용히 마지막 요소를 반환합니다.
포인터를 이동하기 전에 비교하는 경우입니다. 두 포인터 모두 노드 0에서 시작하므로, 루프 맨 위에서 확인하면 모든 목록에서 사이클이 있다고 판단합니다.
순회 경로가 아니라 전체 배열을 살펴보는 경우입니다. [-1, 2, 1]에서는 노드 1과 2가 루프를 이루지만, 헤드는 바로 끝나므로 답은 false입니다. next에서 값이 반복되는지 확인하는 것도 잘못된 방법입니다. [4, 4, 4, 4, -1]에서는 여러 노드가 노드 4를 가리키지만 사이클은 없습니다.
사이클이 반드시 헤드로 돌아와야 한다고 가정하는 경우입니다. [1, 2, 3, 4, 4]에서는 마지막 노드가 자기 자신을 가리키고, [0]에서는 헤드가 자기 자신을 가리킵니다.

자주 묻는 질문4

플로이드의 순환 탐지는 어떻게 작동하나요?

두 포인터가 헤드에서 시작합니다. 하나는 한 번에 링크 하나씩, 다른 하나는 두 개씩 이동합니다. 순환이 없으면 빠른 포인터가 끝에 도달합니다. 순환이 있으면 두 포인터 모두 순환 안에 들어가고, 빠른 포인터는 매 단계 노드 하나씩 거리를 좁혀 같은 노드에서 만납니다.

연결 리스트 사이클의 시간 및 공간 복잡도는 어떻게 되나요?

두 접근 방식 모두 모든 노드를 제한된 횟수만큼 방문하므로 O(n) 시간이 걸립니다. 방문한 노드를 표시하려면 O(n)의 추가 메모리가 필요합니다. Floyd의 빠른 포인터와 느린 포인터는 노드 번호 두 개만 사용하므로 O(1)이 필요합니다.

빠른 포인터가 느린 포인터를 건너뛸 수 없는 이유는 무엇인가요?

사이클 내부에서는 각 라운드마다 fast는 노드 두 개를 이동하고 slow는 한 개를 이동하므로, fast가 slow에 도달하기 위해 이동해야 하는 거리는 정확히 1씩 줄어듭니다. 라운드마다 1씩 줄어드는 거리는 3, 2, 1, 0이 되며 0을 지나칠 수 없으므로 두 포인터는 한 노드에서 만납니다.

단계를 세어 순환을 감지할 수 있나요?

이 배열 형태에서는 그렇습니다. 순환이 없는 리스트는 n번의 링크 이동 안에 -1에 도달하므로, 끝에 도달하지 않고 n번의 링크를 이동하면 순환이 있다는 것을 증명할 수 있으며, 메모리는 O(1)만 사용합니다. 이 방법은 노드의 개수가 필요한데, 포인터로 이루어진 리스트에서는 노드의 개수를 알 수 없고, 순환이 있으면 먼저 노드 수를 세는 작업이 끝나지 않습니다. Floyd의 방법에는 개수를 셀 필요가 없습니다.

Python

def hasCycle(next):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

next = [1, 2, 3, 1]

기대값

true