[Leetcode][160] Intersection of Two Linked Lists

문제 : leetcode.com/problems/intersection-of-two-linked-lists/

---

2개의 연결리스트가 주어질 때, 교차점이 시작되는 노드를 찾아라.

교차점이 시작되는 노드 이후의 노드들은 두 개의 연결리스트에서 모두 같다.

---

예시로 나온 listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]로 살펴보자.

listA-listB

listB-listA

를 순서대로 연결한뒤 앞에서부터 하나씩 비교하다보면 교차점이 시작되는 노드를 찾을 수 있다.

 

[4,1,8,4,5-5,6,1,8,4,5]

[5,6,1,8,4,5-4,1,8,4,5]

 

위와같이 연결해서 앞에서부터 하나씩 비교하면 언젠가는 교차점이 되는 8을 찾을 수 있다.

만일 탐색이 끝날때까지 같아지는 노드를 찾을 수 없다면 교차점이 없는 경우이다.

 

시간복잡도는 listA, listB 길이를 각각 N, M이라 했을 때, O(N+M)

 

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/160.%20Intersection%20of%20Two%20Linked%20Lists.cpp