연결 리스트 문제를 풀다 보면 값이 같은지를 보는 문제가 아니라, 노드 자체가 같은 객체인지를 판단해야 하는 경우가 있습니다.
이번 글에서는 두 개의 단방향 작업 체인이 중간부터 같은 후속 단계를 공유할 때, 가장 처음으로 겹치는 노드를 찾는 방법을 정리해보겠습니다.
핵심은 해시셋 없이도 풀 수 있는 포인터 전환 기법입니다.
문제
두 개의 단방향 연결 구조가 있습니다.
처음 부분은 서로 다를 수 있지만, 어느 순간부터는 같은 노드를 공유하며 끝까지 이어질 수 있습니다.
이때 두 구조가 처음으로 합쳐지는 노드를 찾아 반환하세요.
조건은 다음과 같습니다.
- 사이클은 없습니다.
- 시간 복잡도는
O(M + N)을 목표로 합니다. - 추가 공간은
O(1)만 사용합니다.
예시
다음과 같은 두 체인이 있다고 해보겠습니다.
Chain A: 5 → 11 → 21 → 34
Chain B: 8 → 2 → 21 → 34
여기서 21 → 34 구간은 값만 같은 것이 아니라,
실제로 같은 노드 객체를 공유하는 구간입니다.
따라서 정답은 값이 21인 노드입니다.
중요한 점은 다음입니다.
값이 같다고 무조건 같은 노드는 아니다.
문제는 '값'이 아니라 '노드 객체'를 찾아야 한다.
처음 떠오르는 방법
가장 단순한 방법은 한 체인의 모든 노드를 Set에 넣고,
다른 체인을 순회하면서 이미 본 노드인지 확인하는 것입니다.
이 방식은 이해하기 쉽지만, 추가 메모리가 필요합니다.
이번 문제는 다음 조건을 만족하는 풀이가 더 좋습니다.
시간 복잡도: O(M + N)
공간 복잡도: O(1)
즉, 체인을 각각 한 번씩만 훑고, 별도 자료구조는 쓰지 않는 방법이 필요합니다.
핵심 아이디어
포인터 두 개를 둡니다.
pA는 A 체인에서 시작pB는 B 체인에서 시작
각 포인터는 한 칸씩 이동합니다.
그런데 끝에 도착하면 멈추지 않고, 반대쪽 체인의 시작점으로 옮깁니다.
즉 이동 경로는 다음처럼 됩니다.
pA: A 전체를 걷고 → B 전체를 걷는다
pB: B 전체를 걷고 → A 전체를 걷는다
이렇게 하면 두 포인터가 이동하는 총 길이가 같아집니다.
교차 지점이 있다면 결국 같은 노드에서 만나고,
없다면 둘 다 null에서 만나게 됩니다.
코드
function findFirstSharedNode(headA, headB) {
let pA = headA;
let pB = headB;
while (pA !== pB) {
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}
return pA;
}
코드 해설
1. 두 포인터 준비
let pA = headA;
let pB = headB;
각 체인의 시작점에서 포인터를 하나씩 출발시킵니다.
2. 노드 객체가 같아질 때까지 반복
while (pA !== pB) {
여기서 중요한 건 값 비교가 아니라 참조 비교입니다.
아래처럼 값만 비교하면 안 됩니다.
pA.value === pB.value
이건 값이 우연히 같을 뿐, 서로 다른 노드일 수도 있기 때문입니다.
우리가 확인해야 하는 건:
pA === pB
즉, 두 포인터가 정말 같은 노드 객체를 가리키는지입니다.
3. 끝에 도달하면 반대 체인으로 이동
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
이 부분이 풀이의 핵심입니다.
pA는 A 체인을 다 걷고 나면 B 체인의 시작점으로 갑니다.
pB는 B 체인을 다 걷고 나면 A 체인의 시작점으로 갑니다.
이 과정 덕분에 두 포인터는 길이 차이를 자연스럽게 맞추게 됩니다.
왜 이 방식이 되는가?
두 체인의 앞부분 길이가 다르면, 처음에는 두 포인터의 위치가 어긋나 있을 수 있습니다.
예를 들어 A의 독립 구간이 더 길면 pA가 먼저 더 많이 걷습니다.
하지만 한 번 끝까지 간 뒤 반대편 체인을 걷게 하면 두 포인터가 이동한 총 거리는 결국 같아집니다.
pA 이동 거리 = A 길이 + B 길이
pB 이동 거리 = B 길이 + A 길이
총 이동 거리가 같아지면, 공유 구간이 있다면 같은 시점에 같은 노드로 진입하게 됩니다.
그래서 교차 지점에서 만나게 됩니다.
예제로 따라가기
Chain A: 5 → 11 → 21 → 34
Chain B: 8 → 2 → 21 → 34
처음 상태:
pA: 5
pB: 8
한 칸씩 이동:
pA: 11
pB: 2
다시 이동:
pA: 21
pB: 21
이제 두 포인터가 같은 노드를 가리키므로 반복을 멈추고,
값이 21인 노드를 반환합니다.
교차 지점이 없는 경우
만약 두 체인이 전혀 만나지 않는다면,
두 포인터는 결국 둘 다 null이 됩니다.
예를 들어:
Chain A: 1 → 4 → 7
Chain B: 2 → 5 → 9
이 경우에도 포인터는 끝까지 갔다가 서로의 체인을 다시 걷고,
마지막에는 null에서 만나게 됩니다.
따라서 반환값은 null입니다.
복잡도
| 구분 | 복잡도 |
|---|---|
| 시간 복잡도 | O(M + N) |
| 공간 복잡도 | O(1) |
각 포인터는 최대 두 체인을 한 번씩만 지나갑니다.
별도의 배열, Set, Map 같은 자료구조를 쓰지 않으므로 공간도 상수입니다.
헷갈리기 쉬운 부분
1. 값이 같다고 같은 노드는 아니다
이 문제는 값이 같은 위치를 찾는 문제가 아닙니다.
같은 메모리의 노드 객체를 찾는 문제입니다.
즉, 비교는 항상 참조 기준이어야 합니다.
2. 왜 길이를 먼저 맞추지 않아도 되는가?
길이를 따로 재서 긴 쪽을 먼저 이동시키는 풀이도 가능합니다.
하지만 포인터 전환 방식은 길이 계산 없이도 두 포인터의 총 이동 거리를 같게 만들어 줍니다.
그래서 구현이 더 짧고 깔끔합니다.
3. 만나는 지점이 없을 수도 있다
교차 지점이 없으면 무한 루프가 되는 것이 아니라,
두 포인터가 결국 null에서 같아집니다.
그래서 별도의 예외 처리 없이 같은 반복문으로 해결됩니다.
정리
이번 문제의 핵심은 값 비교가 아니라, 노드 객체 자체가 같은지를 찾는 것입니다.
포인터 두 개를 두고:
한쪽 체인을 다 걷고
반대쪽 체인으로 넘어가게 만들면
두 포인터의 총 이동 거리가 같아진다
이 원리 덕분에 추가 메모리 없이 첫 공통 노드를 찾을 수 있습니다.
정리하면 포인트는 다음과 같습니다.
같은 값이 아니라 같은 노드 객체를 찾는다
끝에 도착하면 반대 체인으로 전환한다
공유 구간이 있으면 거기서 만나고, 없으면 null에서 만난다
짧은 코드지만, 길이 차이를 자연스럽게 상쇄하는 아이디어가 담긴 좋은 투 포인터 문제입니다.