greentea31's Note

https://leetcode.com/problems/palindrome-linked-list/

풀이 과정

링크드 리스트의 시작 포인터를 입력 받아서, 전체 링크드 리스트의 데이터가 팰린드롬인지 확인하는 문제이다.

팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬이라 한다.

문제를 해결하는 방법은 2가지가 떠오른다.

1. 링크드 리스트의 데이터들을 Deque에 전부 다 저장해놓고 Deque.popleft(), Deque.pop()을 해가면서 앞, 뒤 원소가 같은지 체크해가기.

2. 링크드 리스트를 2칸씩 뛰어가며 순회하는 fast, 1칸씩 뛰어가며 순회하는 slow를 두면 fast가 순회를 마치면 slow는 링크드 리스트의 절반까지 순회했을 것이라 기대할 수 있다. slow로 순회할 때 여태 순회했던 링크드 리스트의 원소를 역순으로 가지고 있는 새로운 링크드 리스트를 만들고, slow가 절반까지 순회했으면 절반 이후의 나오는 데이터들과 역순 링크드 리스트의 데이터가 같은지 아닌지를 확인하는 방법이 있다.

a -> b -> c -> b -> a의 링크드 리스트가 존재한다면,

fast: a -> c -> a

slow: a -> b -> c 순으로 순회가 진행되고 역순 링크드 리스트 c -> b -> a가 만들어진다. 전체 링크드 리스트의 중간부터의 링크드 리스트가 c -> b -> a 이고, 역순 링크드 리스트가 c -> b -> a이니 팰린드롬 문자열로 이루어진 링크드 리스트라고 판단할 수 있는 것이다.

소스 코드

deque 풀이

import collections

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        temp = collections.deque()
        while head.next is not None:
            temp.append(head.val)
            head = head.next
        temp.append(head.val)
        while len(temp) > 1:
            if temp.popleft() != temp.pop():
                return False
        return True

링크드 리스트 풀이

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        slow = fast = head
        
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
            
        if fast: # 길이가 홀수면
            slow = slow.next # 한칸 더
        
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        
        return not rev