[LeetCode] 234. Palindrome Linked List [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Palindrome Linked List - LeetCode>

1. 문제 (팰린드롬 연결리스트)

연결리스트가 팰린드롬인지 확인하라.

2. 풀이

1. deque를 이용한 풀이
2. 런너 기법을 이용한 풀이

3. 코드

• deque를 이용한 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from collections import deque
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 종료 조건
        if not head:
            return True

        que, node = deque(), head
        while node:
            que.append(node.val)
            node = node.next

        # 팰린드롬 확인
        while len(que) > 1: # 홀수인 경우 중앙에 1개가 남음
            if que.popleft() != que.pop():
                return False

        return True

• 런너 기법을 이용한 풀이

(출처)

# 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: 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: # 홀수인 경우 중앙에 1개가 남음
            slow = slow.next   

        # 팰린드롬 확인
        while slow and slow.val == rev.val:
            slow, rev = slow.next, rev.next

        return not slow

• 결과 :

방식	Status	Runtime	Memory	Language
deque	[Accepted]	52 ms	24.3 MB	python3
런너 기법	[Accepted]	68 ms	24.1 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋