[파이썬 알고리즘 인터뷰] 12. 팰린드롬 연결리스트

1. 문제

leetcode 234. palindrome linked list
한방향 연결리스트의 head가 주어지면, 주어진 연결리스트가 팰린드롬(뒤집어도 내용이 변하지 않음)이면 True를 리턴하여라.

주어진 한방향 연결리스트는 다음과 같다.

2. 연결리스트를 배열로 바꾸어 풀기

팰린드롬 여부를 확인하기 위해서는 양쪽에서 탐색을 동시에 진행할 수 있어야한다. 한반향 연결리스트는 양방향 탐색이 어렵기 때문에 연결리스트를 배열로 바꾸어 풀었다. 먼저 연결리스트의 값을 저장할 배열 arr을 만들었다. 그리고 연결리스트가 끝날때까지 head.next로 리스트를 탐색하며 head.val을 arr에 추가했다. 마지막으로는 arr을 뒤집은 arr[::-1]이 arr과 같은지 여부를 리턴한다.

3. 런너를 활용한 풀이

연결리스트를 다른 자료형으로 바꾸지 않고 푸는 방법도 있다. 속도가 2배 차이가 나는 2개의 포인터를 이용해서 중간지점을 찾는 런너를 활용하는 방법이다.
먼저 slow와 fast 두 포인터를 모두 head를 가리키게 한다. 그리고 이 slow는 매번 하나의 노드를, fast는 매번 2개의 노드를 탐색한다. 이와 동시에 매번 탐색 때마다 slow가 가리키고 있는 노드를 rev가 가리키게 하면서 역순 연결리스트를 만든다. 그리고 fast가 연결리스트의 끝에 이르면, slow가 가리키는 연결리스트의 남은 부분과 rev가 가리키는 지금까지 탐색한 연결리스트의 길이가 일치하게 된다.  
그러면 이 지점부터 rev와 slow의 값을 비교하며 연결리스트가 팰린드롬인지 확인한다. 다만 연결리스트의 노드가 홀수개인 경우에는 가운데 노드는 비교할 필요가 없기 때문에 slow 포인터를 하나 더 앞으로 가게 한뒤에 rev와 slow를 비교한다.