CTCI | 교집합

두 Linked List의 교집합이 되는 첫번째 노드를 찾아라

두 Linked List가 주어졌을 때, 값이 같은게 아닌, 주소가 같은 노드를 찾아내는 문제이다. 우선 이 LinkedList가 교집합이 없을수도 있고, 두 LinkedList의 길이는 물론 다를것이다. 제일 먼저 떠오르는 방법은, 포인터를 2개 이용하는 방법인데, 첫 리스트의 노드를 outter loop같이 늦게 하나씩 비교하고, 다른 리스트의 노드들을 계속 돌면서 비교하는 방법이다. 하지만, 이 방법은 시간이 많이 쓰인다. N의 노드를 N번 비교해야하기 때문에, O(N^2)만큼의 Time Complexity가 발생한다. Space는 따로 사용하지 않기때문에 O(1) 이다. 우선, 이 breadth force algorithm을 이용해 로직을 작성해보자.

 

Node intersection(Node l1, Node l2){
	// check if either l1 or l2 are null
    if(l1 == null || l2 == null){
    	return null;
    }

	while(l1 != null){
    	Node curr = l2;
        while(curr != null){
        	if(l1 == curr){
            	return curr;
            }
            curr = curr.next;
        }
        l1 = l1.next;
    }
    
    // didn't find any intersection
    return null;
}

 

이 알고리즘보다 더 효율적인 방법이 있을까? 바로 노드의 숫자를 이용하는 방법이다. 두 노드는 어떤 교집합을 공유할것이다. 그리고 이 리스트들은 다른 길이를 가지고 있을텐데, 그렇다고 해도, 한걸음씩 이동한 후, 먼저 null에 도달했다면, 그 노드는 다른 리스트보다 짧은 길이를 갖고있다. 그때, 그 포인터를 현재가 아닌 다른 리스트의 맨 처음으로 보내고, 또 다른 리스트도, null에 도달했을 때, 거꾸로 이전에 먼저 null에 도달한 리스트의 맨 앞으로 포인트를 옮겨주게 되면, 두 포인터는 결국 intercept에서 만나게 된다. 

 

Node intercept(Node l1, Node l2){
	if(l1 == null || l2 == null){
    	return null;
    }
    
    Node p1 = l1;
    Node p2 = l2;
    while(p1 == null || p2 == null){
    
    	// 끝에 도달하면, 다른 리스트의 맨 앞으로 보낸다.
    	if(p1 == null) p1 = l2;
        if(p2 == null) p2 = l1;
        
        if(p1 == p2) return p1;
        p1 = p1.next;
        p2 = p2.next;
    }
    
    return null
}

 

여기서 중요한 개념은 두 리스트를 동시에 순회하면서, 한 리스트의 끝에 도달하면 다른 리스트의 시작으로 이동시키는 것이다. 이 방법은 두 리스트가 교차점을 공유할 경우, 최종적으로 교차점에서 두 포인터가 만나게 하는 효과적인 방법이다. 두 리스트의 길이가 다를 수 있다. 가정해보면, 하나의 리스트가 다른 리스트보다 더 길다면, 더 긴 리스트의 포인터가 끝에 도달하는 시점에, 짧은 리스트의 포인터는 교차점에 있지 않을 가능성이 높다. 그래서, 각 포인터가 자신의 리스트 끝에 도달하면, 다른 리스트의 시작으로 이동했다. 이렇게 함으로써, 각 포인터는 두 리스트의 길이 합(N+M)만큼 이동하게 되는데, 두 포인터가 각각 다른 리스트로 이동한 후, 다시 순회를 시작하면, 이전에 더 길었던 리스트의 추가적인 길이를 '상쇄'시키고, 두 포인터가 교차점에 동시에 도착하도록 만든다. 두 리스트가 교차점을 공유한다면, 두 포인터는 결국 동일한 노드를 가리키게 된다. 만약 교차점이 없다면, 두 포인터는 리스트의 끝(null)에서 만나게 된다.

 

시간 복잡도: O(N+M), 여기서 N과 M은 각각 두 리스트의 길이이다. 이 알고리즘은 각 리스트를 최대 한 번씩만 순회하기 때문에, 두 리스트의 전체 길이에 비례하는 시간이 소요된다.

공간 복잡도: O(1), 추가적인 공간을 사용하지 않고 입력으로 주어진 리스트만을 사용하여 문제를 해결한다.

 

 

 

 

Reference

https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2002.%20Linked%20Lists/Q2_07_Intersection/Question.java

CtCI-6th-Edition/Java/Ch 02. Linked Lists/Q2_07_Intersection/Question.java at master · careercup/CtCI-6th-Edition