160. Intersection of Two Linked Lists

2026-03-19
leetcode
리트코드 160번 풀이

문제

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에 저장