234. 팰린드롬 연결 리스트

234. Palindrome Linked List
Easy
파이썬 알고리즘 인터뷰 201p

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

♬idea

• 빗물 트래핑에서 썼던 투 포인터를 활용할 수 있을 것 같다.
• 런너를 사용한 역순 연결 리스트 작성을 통해 해결할 수 있을 것 같다.

 

1. 리스트와 투 포인터 사용

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        pal = []
        
        #리스트로 만들어주기
        while head:
            pal.append(head.val)
            head = head.next
            
        left, right = 0, len(pal) - 1
        
        #투 포인터 사용하여 비교
        while left <= right:
            if pal[left] != pal[right]:
                return False
            left += 1
            right -= 1
        
        return True

교재에서는 리스트로 변환하여 pop() 함수를 활용해 풀이한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        q:List = []
        
        if not head:
            return True
        
    
        node = head
        #리스트 변환
        while node is not None:
            q.append(node.val)
            node = node.next
            
        #팰린드롬 판별
        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False
            
        return True

 

2. Runner & 역순 연결 리스트

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        prev = None
        
        # runner
        while fast and fast.next:
            fast = fast.next.next
            prev, prev.next, slow = slow, prev, slow.next
            
        if fast:
            slow = slow.next
            
        while prev and prev.val == slow.val:
            slow, prev = slow.next, prev.next
            
        return not prev

 

리트코드 876번, 206번 참조