서로 다른 두 연결리스트의 교차점 찾기

leetcode 160. Intersection of Two Linked Lists 문제풀이.

문제: 서로 다른 두 연결리스트가 주어졌을 때, 첫 교차점을 찾아라.

A와 B 리스트가 주어졌을 때 c1노드를 반환

 

교차되는 노드가 없다면 null을 반환

 

Hash Set

1. A 리스트를 먼저 순회하며 hash set에 노드들을 저장한다.

2. B 리스트 순회하며 노드들이 이미 hash set에 저장되어있는지 확인한다.

   이미 저장되어 있다면 해당 노드를 반환한다.

3. 무사히 B리스트 순회를 마지막 노드까지 마쳤다면, 교차되는 노드가 없다는 뜻이므로 null을 반환한다.  

Floyd's Tortoise and Hare algorithm

이 문제 또한 토끼와 거북이 알고리즘으로 메모리를 사용을 O(1)으로 줄여줄 수 있다.

Time Complexity: O(N)

Space Complexity: O(1)

 

1. A리스트의 마지막 노드가 B리스트의 첫번째 노드를 가르키도록한다.

   만약 두 연결리스트가 교차점을 가지고 있다면 A+B리스트는 사이클을 가지고 있을 것.

A리스트 tail node가 B리스트 head를 가르키게하기 예시

2. 각 iteration마다 거북이포인터를 1번 토끼 포인터를 2번씩 움직여 교차점을 찾는다.

   교차점이 없다면 토끼 포인터가 null값이 되어 반복문을 빠져나오게된다.

거북이가 F만큼 이동했을 때 => F+C-h만큼 이동했을 때

3. 교차되는 노드가 있다면 A+B리스트의 헤드와 첫 교차점을 각 같은 속도로 이동시켜 사이클이 시작되는 노드를 찾는다. (교차되는 노드가 없다면 이 단계는 실행되지 않는다)

F=b 등식이 성립하기 때문에 방법 3으로 사이클이 시작되는 첫 부분을 찾을 수 있다. 

4. 답을 반환하기 전에는 A리스트의 테일 노드가 null을 가르키도록 수정한다.

   (조작한 부분을 원상복구 하는 것)