문제은행으로

CS 기초·알고리즘

두 연결 리스트의 첫 교차 노드

두 단방향 연결 리스트가 뒤쪽 노드를 공유할 수 있습니다. 값이 같은 노드가 아니라 실제로 처음 공유하는 노드를 O(n) 시간, O(1) 추가 공간으로 찾는 방법을 설명해 주세요.

내 답변

면접관 모드

짧은 답 보기

두 리스트의 길이를 각각 세어 긴 쪽 포인터를 길이 차만큼 먼저 보낸 뒤 둘을 한 칸씩 같이 전진시키며 ===로 같은 인스턴스인지 비교하면, 처음 같아지는 노드가 교차점이고 끝까지 없으면 nil이다.

받은 질문 공유