문제
Intersection of Two Linked Lists
풀이
아이디어
두 리스트를 동시에 순회하면서 방문한 노드를 Set에 저장한다. 이미 Set에 있는 노드를 다시 만나는 순간, 그 노드가 교차점이다. 두 리스트에 사이클이 없으므로, Set에 중복으로 등장하는 노드는 반드시 상대 리스트에서 온 것임이 보장된다.
코드
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {let ptrA = headA,ptrB = headB;let nodeSet = new Set();while (ptrA !== null || ptrB !== null) {if (ptrA !== null) {if (nodeSet.has(ptrA)) return ptrA;nodeSet.add(ptrA);ptrA = ptrA.next;}if (ptrB !== null) {if (nodeSet.has(ptrB)) return ptrB;nodeSet.add(ptrB);ptrB = ptrB.next;}}return null;}
시간 / 공간 복잡도
- 시간 복잡도: O(max(n, m)) — 두 리스트 전체 순회 (교대로 진행하므로 max(n, m))
- 공간 복잡도: O(n + m) — 모든 노드를 Set에 저장
end