[Leetcode] 리트코드 - 팰린드롬 연결 리스트(Palindrome Linked List) 파이썬(python) 풀이

팰린드롬 연결 리스트

문제 링크

code

class ListNode():
    def __init__(self, x):
        self.val  = x
        self.next = None

class Solution():
    def isPalindrome(self, head: ListNode) -> bool:
        rev = None
        slow = fast = head

        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
            # 역순으로 연결 리스트 rev를 생성하는 로직을 slow 앞에 덧붙인다.

        if fast:
            slow = slow.next

        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next

        return not rev

l = ListNode(1)
l.next = ListNode(2)
l.next.next = ListNode(2)
l.next.next.next = ListNode(1)

print(Solution().isPalindrome(l))

런너 기법

연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다.

2개의 포인터는 각각 빠른 런너, 느린 런너라고 부르는데, 대개 빠른 런너는 두 칸씩 건너뛰고 느린 런너는 한 칸씩 이동하게 한다. 이 때 빠른 런너가 연결 리스트의 끝에 도달하면, 느린 런너는 정확히 연결 리스트의 중간 지점을 가리키게 된다. 이 같은 방식으로 중간 위치를 찾아내면, 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러모로 활용할 수 있어 연결 리스트 문제에서는 반드시 쓰이는 기법이기도 하다.

Solution : 런너

런너 기법을 활용한다. 입력 값이 1->2->3->2->1인 연결 리스트에 Runner를 적용해 풀이하는 방법을 도식화하면 밑과 같다.

(위 그림에서 rev = 2 → 1 → None에서 끝나고 rev = 3 → 2 → 1 → None는 잘못된 그림)

빠른 런너와 느린 런너를 각각 출발시키면, 빠른 런너가 끝에 다다를 때 느린 런너는 정확히 중간 지점에 도달하게 될 것이다. 느린 런너는 중간까지 이동하면서 역순으로 연결 리스트 rev를 만들어 나간다. 이제 중간에 도달한 느린 런너가 나머지 경로를 이동할 때, 역순으로 만든 연결 리스트의 값들과 일치하는지 확인해나가면 된다.

입력값이 홀수일 때와 짝수일 때 마지막 처리가 다른데, 홀수일 때는 slow 런너가 한 칸 더 앞으로 이동하여 중앙의 값을 빗겨 나가야 한다. 왜냐하면 여기서 3은 중앙에 위치한 값으로, 팰린드롬 체크에서 배제되어야 하기 때문이다. (slow와 역순 리스트를 비교하기 때문에 slow를 12321 테스트 케이스에서는 2부터 rev랑 비교하게 해야함)

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]