Intersection of Two Linked Lists
두 개의 단일 연결 리스트가 하나의 노드 풀에 있습니다. 노드 i는 노드 next[i]를 가리키며, -1은 리스트의 끝을 나타냅니다. 리스트 A는 노드 headA에서 시작하고 리스트 B는 노드 headB에서 시작합니다. 노드는 특별한 순서 없이 저장되어 있으므로 링크를 따라가세요.
두 리스트는 중간에 합쳐질 수 있습니다. 즉, 어떤 노드부터 끝까지 같은 노드들을 계속 거칠 수 있습니다. 두 리스트에 모두 포함된 첫 번째 노드의 인덱스를 반환하세요. 공통 노드가 없으면 -1을 반환하세요.
함수
- nextinteger-array
- 각 노드가 연결하는 노드의 인덱스 또는 목록의 마지막 노드인 경우 -1
- headAinteger
- 리스트 A의 첫 번째 노드
- headBinteger
- 리스트 B의 첫 번째 노드
- 반환값integer
- 두 목록이 공유하는 첫 번째 노드 또는 -1
제약 조건
2 ≤ n ≤ 104이며, 여기서n은next의 길이입니다.- 각
next[i]는-1이거나0부터n-1까지의 노드 인덱스입니다. 0 ≤ headA, headB ≤ n-1이고headA ≠ headB입니다.- 두 목록 모두 노드를 두 번 방문하지 않고
-1에서 끝납니다. 순환은 없습니다. - 모든 노드는 목록 A에 있거나, 목록 B에 있거나, 두 목록 모두에 있습니다.
예제
- 입력
- next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
- 출력
- 1
- 설명
- A는
3, 5, 1, 4, 0을 방문하고 B는2, 1, 4, 0을 방문합니다. 노드1부터 두 경로는 모든 노드를 공유하며, A의 그 이전 노드 중 B에 있는 노드는 없으므로 답은1입니다.
- 입력
- next = [2, 3, 4, -1, -1]headA = 0headB = 1
- 출력
- -1
- 설명
- 리스트 A는
0, 2, 4이고 리스트 B는1, 3입니다. 두 리스트 모두 공통 노드에 닿지 않고-1에서 끝나므로 답은-1입니다.
- 입력
- next = [3, 2, 0, -1]headA = 1headB = 0
- 출력
- 0
- 설명
- 리스트 A는
1, 2, 0, 3이고 리스트 B는0, 3입니다. 리스트 B는 리스트 A의 꼬리이므로, 처음으로 공유하는 노드는headB자체인 노드0입니다.
후속 질문
추가 메모리 O(1)을 사용하여 O(m + k) 시간 안에 노드를 찾을 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
노드에는
next가 하나 있습니다. 두 리스트가 같은 노드에 도달한 뒤에 다시 서로 갈라질 수 있을까요? 두 리스트의 형태에 대해 무엇을 알 수 있나요?두 리스트의 길이가 같다면 나란히 따라가다가 두 포인터가 같은 노드에 도달했을 때 멈출 수 있습니다. 문제는 더 긴 리스트의 시작 부분에 있는 추가 노드입니다. 두 포인터가 어떻게 같은 총 거리를 이동하게 할 수 있을까요?
포인터
a를 리스트 A를 따라 이동시키고, 끝을 벗어나면headB에서 다시 시작하세요.b도 똑같이 하고,headA에서 다시 시작하세요.a == b가 되면 멈추세요. 그 노드 또는-1이 정답입니다.
풀이
노드에는 next가 하나 있으므로, 만나는 두 리스트는 다시 갈라지지 않습니다. 두 개의 개별 시작점이 하나의 공통 꼬리로 이어지는 Y 모양을 이루며, 답은 접점입니다. 시작점까지의 길이가 다를 수 있으므로 두 리스트를 함께 진행하면 접점을 놓칩니다. 아래에서 m과 k는 A와 B의 길이입니다.
A의 각 노드를 B의 모든 노드와 비교합니다
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
포인터는 노드 인덱스이며, 다음으로 이동하는 것은 node = next[node]입니다. A의 각 노드 a를 순서대로 살펴보면서 B의 모든 노드를 순회하고 각 노드를 a와 비교합니다. 일치하는 첫 번째 a가 답입니다. 그보다 앞선 A의 노드는 모두 이미 일치하지 않았기 때문입니다. A의 각 노드마다 B를 다시 훑습니다. 각 리스트에 노드가 5000개씩 있고 공유 노드가 없다면, 비교 횟수는 2.5 × 10^7입니다.
알고리즘
a = headA로 설정합니다.a가-1이 아닌 동안b를headB에서-1까지 이동합니다.- 어느 시점에서든
b == a이면a를 반환합니다. - 그렇지 않으면
a = next[a]로 이동하고 반복합니다. - 리스트 A가 끝나면
-1을 반환합니다.
def getIntersectionNode(next, headA, headB):
a = headA
while a != -1:
# Is node a also on list B? Walk all of B to find out.
b = headB
while b != -1:
if a == b:
return a
b = next[b]
a = next[a]
return -1목록 B의 노드에 표시하세요
핵심 아이디어
각 노드에 대해 “이 노드는 B에 있는가?”를 한 번씩 확인하세요. B를 순회하며 크기가 n인 불리언 배열에 각 노드를 표시합니다. 노드 인덱스는 작은 정수이므로 배열로 해시 집합을 대신할 수 있습니다. 그런 다음 A의 헤드부터 순회합니다. 처음 표시된 노드는 두 목록 모두에 있으며, A를 순서대로 순회하므로 이것이 그런 노드 중 첫 번째입니다. 첫 번째 예제에서 B는 2, 1, 4, 0을 표시하고, A를 순회하면 3과 5를 지나 1에서 멈춥니다. 각 목록을 한 번씩 순회하므로, n개의 표시 공간을 사용하는 대신 시간 복잡도는 O(m + k)입니다.
알고리즘
n개의 불리언 값이 모두 false로 설정된 배열onB를 만듭니다.headB부터 리스트 B를 순회하며 각 노드에 대해onB[node] = true로 설정합니다.headA부터 리스트 A를 순회합니다.onB[node]가 true인 첫 번째 노드를 반환합니다.- 리스트 A가 끝나면
-1을 반환합니다.
def getIntersectionNode(next, headA, headB):
# Mark every node of list B.
on_b = [False] * len(next)
node = headB
while node != -1:
on_b[node] = True
node = next[node]
# The first marked node on list A is the meeting point.
node = headA
while node != -1:
if on_b[node]:
return node
node = next[node]
return -1목록을 전환하는 두 포인터
핵심 아이디어
각 리스트를 접합 지점에서 나눠 보세요. A에는 x개의 전용 노드 다음에 공유 노드 c개가 있고, B에는 y개의 전용 노드 다음에 동일한 c개가 있습니다. 포인터 a는 A를 따라가고, -1로 이동한 다음 headB에서 다시 시작하여 x + c + 1 + y번 이동한 뒤 접합 지점에 두 번째로 도달합니다. 포인터 b는 B를 따라간 다음 A를 따라가며, y + c + 1 + x번 이동한 뒤 도착합니다. 총 이동 횟수는 같습니다. 첫 번째 예시에서 x = 2, y = 1, c = 3이고, 두 포인터 모두 일곱 번 이동한 뒤 노드 1에 도달합니다.
공유되는 꼬리가 없으면 두 포인터는 m + 1 + k번 이동한 뒤( m = k이면 m번 이동한 뒤) 모두 -1에 도달하고, 루프는 -1을 반환합니다. 각 포인터가 전환하기 전에 -1로 이동하는 이유는 두 포인터가 같은 지점에서 멈추기 때문입니다. 각 포인터는 최대 m + k + 1번 이동하며, 인덱스 두 개만큼의 메모리를 사용합니다.
알고리즘
a = headA와b = headB를 설정합니다.a != b인 동안:a가-1이면headB로 이동하고, 그렇지 않으면next[a]로 이동합니다.- 같은 반복에서
b가-1이면headA로 이동하고, 그렇지 않으면next[b]로 이동합니다. - 반복이 끝나면
a를 반환합니다. 이는 처음으로 공유되는 노드이거나-1입니다.
def getIntersectionNode(next, headA, headB):
a, b = headA, headB
# Each pointer walks its own list, then the other one. Both cover
# the same number of nodes, so they reach the meeting node together,
# or reach -1 together when there is none.
while a != b:
a = headB if a == -1 else next[a]
b = headA if b == -1 else next[b]
return a
함정과 경계 사례
- 마지막 노드에서
-1에서 멈추지 않고 곧바로 다른 머리 노드로 이동하는 경우. 두 리스트에 공통 노드가 없으면 포인터는 같은 값을 절대 가리키지 않으며 루프가 무한히 실행됩니다. - 포인터를 각자의 머리 노드에서 다시 시작하는 경우. 그러면 각 포인터는 자신의 리스트를 한 바퀴씩 돌고, 바퀴가 맞물릴 때만 만나므로 최대
(m + 1)·(k + 1)번 이동할 수 있습니다. - 배열의 순서를 리스트의 순서로 취급하는 경우. 노드
0은headA또는headB가 그렇게 지정하는 경우에만 머리 노드이며, 배열에서 이웃한 원소가 리스트에서도 이웃한 노드인 것은 아닙니다. - Lua와 R에서는 배열이 1부터 시작한다는 점을 잊지 마세요. 노드 인덱스는 0부터 시작하도록 유지하고
next[node + 1]을 읽으세요.
자주 묻는 질문3
추가 메모리 없이 두 연결 리스트가 교차하는 지점을 어떻게 찾을 수 있을까요?
두 포인터를 실행합니다. 각 포인터는 자신의 리스트를 따라가다가 끝에 도달하면 다른 리스트의 머리부터 계속 이동합니다. 두 포인터는 같은 총거리를 이동하므로, 첫 번째 공통 노드에 동시에 도달하거나 공통 노드가 없으면 함께 끝에 도달합니다.
리스트의 길이를 비교해서 교집합을 찾을 수 있나요?
네. 두 리스트의 노드 수를 세고, 더 긴 리스트의 포인터를 차이만큼 앞서 이동시킨 다음, 두 포인터가 같아질 때까지 한 번에 한 단계씩 이동합니다. 이 방법도 시간은 O(m + k), 메모리는 O(1)을 사용합니다. 포인터를 전환하는 방법은 두 번의 계수 과정 없이도 같은 정렬을 수행합니다.
두 연결 리스트의 교집합을 찾는 시간 복잡도는 얼마인가요?
두 포인터 방식과 길이 방식은 O(m + k) 시간에 실행되며 추가 메모리는 O(1)입니다. 한 리스트를 집합이나 마크 배열에 저장하는 방법도 선형 시간이 걸리지만 해당 리스트를 저장할 메모리가 필요합니다. 모든 노드 쌍을 비교하면 O(m·k) 시간이 걸립니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def getIntersectionNode(next, headA, headB):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
next = [-1, 4, 1, 5, 0, 1] headA = 3 headB = 2
예상 출력
1