8. 링크드 리스트가 회문(palindrome)인지 알아내는 알고리즘

1. 문제

 링크드 리스트가 회문(palindrome)인지 알아내는 알고리즘을 작성하시오.

 회문(palindrome)은 'abba'나 'madam', 'nurses run' 등등 앞 뒤로 동등한 문장이다.

 '이하이'는 거꾸로 해도 '이하이'와 같은 맥락이다.

 이를 풀어내는 가장 알고리즘은 이렇다.

 1. 리스트의 절반을 탐색한다.

 2. 절반으로 나뉜 리스트의 뒤쪽 리스트를 거꾸로 뒤집는다.

 3. 앞쪽리스트와 뒤쪽리스트와 비교한다.

2. 코드

2-1) 메인

2-2) 알고리즘

2-3) 출력

3. 해설

 이 문제는 간단하다. 먼저 리스트를 절반으로 나눈다. 절반을 찾기 위해서는 전체 길이를 알아야 하기 때문에 O(n)이

걸린다. 다음으로 리스트를 반으로 나눈다. O(n/2)시간이 걸린다. 다음 나눈 리스트 중 하나를 뒤집는다. O(n/2)시간이

걸린다. 마지막으로 앞 뒤의 두 리스트를 비교한다. O(n/2)시간이 걸린다. 

 결론적으로 위의 빅 오 시간을 다 더하면 O(n)+O(n/2)+O(n/2)+O(n/2)이다. 하지만 빅 오 관점에서는 가장 최악의

경우를 고려하므로 결론적으로는 O(n)의 시간이 걸린다. 또한 이 알고리즘을 풀어내는데 생성을 제외하고 추가적으로 

메모리 할당이 없으므로 공간 역시 O(n)이다.