LeetCode 160번 - Intersection of Two Linked Lists

문제

주어진 두 연결 리스트가 교차하고 있는지 확인해서 교차점이 있으면 해당 교차점의 노드를, 없으면 null을 반환하는 문제이다.

---

살펴보기

두 가지 방법을 이용해서 풀어보았다.

 

첫 번째 방법은 두 연결 리스트의 현재 노드부터 교차점까지의 거리를 일치시킨 후, 두 연결 리스트를 동시에 순회하면서 노드의 주소값을 비교하는 방법이다.

 

예를 들어 주어진 두 연결리스트가 아래와 같은 모습을 띈다면

 

빨간색 네모를 친 2칸만큼 파랑색 연결 리스트가 더 길다.

만약 두 연결 리스트를 동시에 순회할 경우, 노랑색 연결 리스트가 파랑색 연결 리스트보다 2칸 앞서가게 돼서, 두 노드의 교차점을 찾을 수 없다..

 

그래서 두 연결 리스트의 길이 차이인 2만큼 파랑색 연결 리스트를 이동한 후 두 연결 리스트를 동시에 순회하면 교차점을 찾을 수 있다.

그러면 이제 길이 차이만 확인하면 된다!

 

두 연결리스트와 연결된 새로운 노드를 만든 후, 두 노드를 이용해 연결 리스트를 순회하면서 각각의 길이를 확인한 후 둘을 비교해서 길이 차이를 확인했다.

 

 

다른 방법으로는 Set를 이용해봤다.

 

둘중 하나의 연결 리스트의 노드 주소를 Set에 전부 저장한 다음, 다른 연결리스트의 노드 주소와 비교하는 방식으로 교차점이 있는지 확인했다.

---

풀어보기

현재 노드부터 교차점까지의 거리를 일치시키는 방법

int lengthA = 0;
int lengthB = 0;

ListNode tempA = headA;
ListNode tempB = headB;

while(tempA != null){
    lengthA++;
    tempA = tempA.next;
}

while(tempB != null){
    lengthB++;
    tempB = tempB.next;
}

if(lengthA > lengthB){
    for(int i=0; i<lengthA - lengthB; i++){
        headA = headA.next;
    }
}

if(lengthA < lengthB){
  for(int i=0; i<lengthB - lengthA; i++){
        headB = headB.next;
    }
}

while(headA != null && headB != null){
    if(headA == headB) return headA;
    headA = headA.next;
    headB = headB.next;
}

return null;

 

Set를 이용하는 방법

Set<ListNode> nodeSet = new HashSet<>();

while(headA != null){
    nodeSet.add(headA);
    headA = headA.next;
}

while(headB != null){
    if(nodeSet.contains(headB)) return headB;
    headB = headB.next;
}
return null;

 

첫 번째 방법의 성능은 1ms, 두 번째 방법의 성능은 6ms로 첫 번째 방법이 훨씬 빨랐다.