[Linked List] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

 

연결된 두개의 Linked List에서 Intersection 노드를 찾는 문제이다

이러한 경우 two pointer를 응용하면 된다

 

예를들어 input : listA = [0,9,1,2,4], listB = [3,2,4]라면

listA: 0 -> 9 -> 1

listB: 3 -> 2 -> 4

순서로 순회할것이다

 

여기부터 listB.next는 none이 된다. 이 경우 다시 얘를 listA의 첫번째 head node로 이어주자

listA: 0 -> 9 -> 1 -> 2 -> 4

listB: 3 -> 2 -> 4 -> 0 -> 9

이제 listA.next가 None이 된다. 역시 listB head를 바라보게 한다.

listA: 0 -> 9 -> 1 -> 2 -> 4 -> 3 -> 2

listB: 3 -> 2 -> 4 -> 0 -> 9 -> 1 -> 2

 

여기서 intersection Node가 걸리게 된다.