7. 두 개의 단일 연결 리스트가 만나는 점 찾기 알고리즘

1. 문제

 다음과 같은 그림에서 초록색 노드를 찾는 알고리즘을 작성하시오.

2. 코드

2-1) 메인

2-2) 교차 리스트 생성 함수

2-3) 메인 알고리즘 함수

2-4) 출력

3. 해설

 이 문제는 아주 간단하다. 2개의 리스트 생성 시간 O(n+m)에 검색시간 O(n)을 더해서 최종적으로 빅오를 따지기에

O(n+m)에 풀린다. 스택이나 다른 방법으로도 충분히 풀어낼 수 있지만 이 포스팅에서는 Hash방법을 이용해서 

풀었다. 메인 알고리즘은 처음 생성한 리스트의 노드 주소를 모두 Hash 테이블에 저장한 뒤, 두 번째 리스트와

Hash 테이블을 같은 노드의 주소가 나올 때까지 비교한다. 

 딱히 어려운 알고리즘은 아니지만 굳이 포스팅한 이유는 Hash라는 기법에 더 익숙해지기 위해서이다. 왜냐하면 모든

기초 알고리즘은 모든 경우를 다 검색하는 Brute Force기법, 정렬을 이용한 기법, 스택이나 큐를 이용한 자료구조를

활용한 기법 그리고 마지막으로 Hash 방법을 사용하여 풀어내는 기법. 총 4가지로 구분되기 때문이다. 앞으로 알고리즘

을 생각할 때에는 위의 순서에 준해서 생각한다.