확실히 알고가야 하는 자료구조, 알고리즘 개념 (6) : LinkedList 교차점 찾기

주어진 두 개의 단방향 LinkedList에서 교차되는 노드를 찾으시오. 단, 값이 아닌 주소로 찾아야 한다.

 

---

노드를 하나하나 비교하면 시간이 과하게 소요됩니다.

 

시간을 줄이기 위해, 노드의 끝을 맞춥니다. (교차된 이후 노드값들은 일치할 것이기 때문입니다.)

 

그 후, 길이가 일치하게끔 보다 긴 리스트의 길이를 자릅니다.

 

그리고부턴 일치되는 

 

private static Node getIntersection (Node l1, Node l2){
	
    //지난번에 만든 LinkedList의 길이를 반환하는 함수를 호출합니다.
    int len1 = getListLength(l1);
    int len2 = getListLength(l2);
    
    //길이가 맞게끔 잘라주는 작업을 합니다.
    if(len1 > len2){
    	l1 = l1.get(len1-len2);
        //이제 자른 후 첫 번째 노드를 변경합니다.
    } else if(len2 > len1){
    	l2 = l2.get(len2-len1);
    }
    //여기 이후 길이가 맞춰졌으니, 비교를 해주면 됩니다.
    while(l1 != null && l2 != null){ //두 리스트 모두 마지막 노드까지 돌립니다.
    	if(l1 == l2){
        	return l1; //같은 노드를 만나면 둘 중 아무 노드나 반환합니다.
        }
        //아직 찾지 못했을 경우, 다음 노드로 넘어갑니다.
        l1 = l1.next;
        l2 = l2.next;
    }
    return null; //Loop가 다 돌 때까지 못찾으면
}