Leetcode :: 234. Palindrome Linked List

Problem

Given the head of a singly linked list, return true if it is a palindrome.

Guess

• 그냥 리스트라면 중간 요소를 구해서 이분 탐색을 했겠지만,

• 연결 리스트 특성 상 반드시 선형 탐색을 해야만 전체 파악이 가능하다.

• 따로 value 리스트를 만들어서 좌우를 비교하자.

Solution 1

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        curr = head

        while curr:
            vals.append(curr.val)
            curr = curr.next

        return vals == vals[::-1]

Solution 2

• Space O(2/n)로 해결할 수 있는 방법 !! (slow, fast pointer 이용)

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

        if fast:
            slow = slow.next

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

        return not rev

• fast 포인터는 두칸씩, slow는 한칸씩 움직인다.

• 고로 fast 포인터가 연결리스트의 끝에 다다랐을 때, slow는 연결리스트의 중앙에 오게 되어있다.

• 따로 역순 링크드 리스트를 두고, 중앙값에 위치한 slow를 끝까지 마저 비교해가며 val이 모두 같은지 비교한다.