[LeetCode] #234. Palindrome Linked List

#234. 팰린드롬 연결 리스트

팰린드롬 이란?
앞뒤가 똑같은 단어나 문장으로, 뒤집어도 똑같은 말이 되는 단어나 문장을 팰린드롬(palindrome)이라고 한다. 우리말로는 '회문'이라고 부르며, racecar, 소주 만 병만 주소와 같은 문장이 해당한다.

문제

문제 링크
singly linked list 1개가 주어졌을 때 팰린드롬인지 판별해라.

풀이1. 리스트

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
    	# 리스트에 요소 넣기
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
		
        # 팰린드롬 판별
        while len(nums) > 1:
            if nums.pop(0) != nums.pop():
                return False

        return True

연결리스트에는 포인터가 있어서 귀찮으니까 포인터가 없는 리스트에 값만 넣어 풀어본다.
숫자를 담을 리스트 nums를 선언한다.
연결리스트 포인터가 끝을 가리킬때까지 연결리스트의 요소를 리스트에 append한다.
숫자를 담은 nums에서 차례대로 처음(왼쪽), 마지막(오른쪽) 요소를 꺼내 같은지 비교한다. 모두 같으면 True, 하나라도 다르면 False를 반환한다.

풀이2. 데크(deque)

import collections
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        nums = collections.deque()
        
        while head:
            nums.append(head.val)
            head = head.next

        # 팰린드롬 판별
        while len(nums) > 1:
            if nums.popleft() != nums.pop():
                return False

        return True

두 번째 방법은 리스트 대신 데크를 사용한다. 아래 두 군데만 바뀐다.

nums = collections.deque()

if nums.popleft() != nums.pop():

동적 배열로 구성되는 리스트는 맨 앞 아이템을 가져오기에 적합한 자료형이 아니다. 첫 번째 값을 꺼내면 모든 값이 한 칸씩 shifting되며 시간 복잡도 O(n)이 발생하기 때문이다.
Deque는 이중 연결 리스트 구조로 양쪽 방향 모두 요소를 추출하는데 시간 복잡도 O(1)에 실행된다.
풀이1, 2 모두 추가적인 공간이 필요하다.

풀이3. 런너(Runner)

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

그림처럼 총 6칸이 있을 때 빠른 런너는 2칸씩 이동하고, 느린 런너는 1칸씩 이동한다. 이동 속도가 다르기 때문에 빠른 런너가 끝에 도달했을 때 느린 런너는 중간 지점에 도달한다.

        def isPalindromeRunner(self, head: ListNode) -> bool:
        slow = fast = head

        # 빠른런너가 끝에 도달할 때까지 loop
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # 나머지 절반 역순으로 만들기
        prev = None
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp
        return prev

        # 팰린드롬 판별
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

1) 연결 리스트의 왼쪽 절반을 구한다.
=> 빠른 런너가 끝에 도달할 때 느린 런너의 위치를 구하면 연결 리스트의 중간 지점을 알 수 있다.
2) 나머지 오른쪽 절반을 역순으로 만든다.
=> #206 참고
3) 두 개의 연결 리스트의 값(val)이 동일한지 비교한다. 값이 모두 동일해야 팰린드롬이며, 하나라도 다르면 팰린드롬이 아니다.

전체 코드

참고
유튜브 강의 NeetCode
책 파이썬 알고리즘 인터뷰