[파이썬 알고리즘] 팰린드롬 연결 리스트

팰린드롬 연결 리스트

리트코드로 풀러 가기

연결 리스트가 팰린드롬 구조인지 판별하라.

입력
1 -> 2
출력
flase

입력
1->2->2->1
출력
true

---

이 문제를 푸는 방법은 크게 두 가지가 있다.

1. 자료구조를 변경
2. 런너를 이용한 풀이

두 가지 모두 틀린 방법은 아니나, 문제의 출제 의도는 2번과 가깝다.

1. 리스트(데크) 로 변환

단순히 팰린드롬의 여부를 판별하는 문제에서 가장 쉽게 생각 할 수 있는 방법은 해당 문자열의 앞, 뒤 부분에서 동시에 pop하며 확인하는 방법이다.

해당 문제에서 주어진 연결 리스트는 앞부분에서 pop하기가 어려우니, list에 각 요소를 append하여 자료형을 바꿔줄 수 있다.

def isPalindrome(head):
    list = []

    if not head:
        return True

    node = head
    while node is not None:
        list.append(node.val)
        node = node.next

    while len(q) > 1:
        if list.pop(0) != list.pop():
            return false

    return True

하지만, 위 풀이는 개선될 여지가 있다.

파이썬의 list에서 pop(0) 연산은 O(n)의 시간을 소모하기 때문이다.

따라서 list 대신 deque를 이용하면 O(1) 의 연산으로 popLeft() 할 수 있다.

선언하는 부분을

list = collections.deque()

로 바꾸고,

list.pop(0) -> list.popleft()

로 바꾸면 된다.

2. 런너를 이용한 풀이

'런너' 풀이 방식은 투 포인터 방식과 비슷한 면이 있다.

속도가 다른 두 '런너'를 동시에 출발 지점(연결 리스트의 head)에서 출발 시키고 난 뒤 이를 알고리즘의 풀이에 활용하는 방식이다.

위 문제에서는 빠른 런너를 두 칸씩 이동시키고, 느린 런너를 한 칸씩 이동시키면 빠른 런너가 끝에 도달했을 때 느린 런너는 중간에 위치하게 된다.

이때, 느린 런너가 지나온 값들을 배열이나 연결 리스트에 저장하고, 앞으로 지나갈 값들과 비교하게 되면 풀이가 완성된다.

그리고, 주어진 연결 리스트의 사이즈가 홀수일 때는, 중간에 위치한 값을 slow가 뛰어넘은 상태에서 reverse와 비교해야 정상적으로 작동하기 때문에, 짝수인 경우 fast의 마지막 값이 None이 아닌 것을 활용하여 검사해줄 수 있다.

# code: linkedList_isPalindrome.py
def isPalindrome(head):
    slow = fast = head

    while fast and fast.next:
        fast = fast.next.next
        reverse, reverse.next, slow = slow, reverse, slow.next

    if fast:
        slow = slow.next

    while reverse and (reverse.val == slow.val):
        slow, reverse = slow.next, reverse.next
    return not reverse