교집합

문제

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

 

예제

해법 #1. 두 리스트의 사이즈를 맞춰준 뒤, 비교한다.

 

• 연결리스트에 교집합이 있다는 말은 두 리스트의 마지막 노드는 항상 같아야 한다는 의미가 된다.
• 두 리스트의 길이를 맞춰준 뒤 비교한다.

public static Node getIntersection(Node l1, Node l2) {
	
	int len1 = lengthOfList(l1);
	int len2 = lengthOfList(l2);
	
	if(len1 > len2) {
		l1 = getKthNode(l1, len1 - len2); // 차이만큼 이동한다.
	} else if(len1 < len2) {
		l2 = getKthNode(l2, len2 - len1);
	}
	
	while(l1 != null && l2 != null) {
		if(l1 == l2) { // 노드가 같은지 확인해준다.
			return l1;
		}
		l1 = l1.next;
		l2 = l2.next;
	}
	return null;
	
}

---

체크포인트:

• 책에서는 위의 해법의 preProcess 과정으로, 두 연결리스트의 마지막 노드를 구하고, 마지막 노드가 다르면 교집합이 없으므로, 비교하는 로직을 수행하지 않았다.
• 실습할때, 리스트를 두개 만들고 비교하면 답이 나오지 않는다. 주소까지 완벽히 동일해야 하기 때문이다.

Github 주소:

https://github.com/mongsilJeong/algorithm/blob/master/src/algorithm/codingInterview/datastructure/linkedList/Intersection.java

mongsilJeong/algorithm