[코딩인터뷰 완전정복] 2.7 교집합

Q : 단방향 연결리스트 두 개가 주어졌을 때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫 번째 리스트에 있는 k번째 노드와 두 번쨰 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다.

 

A : HashSet을 사용한다. 첫 번째 리스트를 순회하며 각 노드의 주소값을 HashSet에 담는다. 두 번째 리스트를 순회하며 노드의 주소값이 HashSet에 있을 경우 해당 노드부터 End노드 까지의 부분 리스트가 두 리스트의 교집합이다.