파이썬 알고리즘 인터뷰 - 13. 팰린드롬 연결 리스트

 

<--- 리트코드 234. Palindrome Linked List --->

# 문제: 연결 리스트가 팰린드롬 구조인지 판별하라.

 

입력

1->2

출력

false

 

입력

1->2->2->1

출력

true

 

 

# 풀이

1. 리스트 변환

from typing import List
 
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None
 
def is_palindrome(head: 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
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(2)
list4 = ListNode(1)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
 
print(is_palindrome(head))

from typing import List
import collections
 
 
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None
 
 
def is_palindrome(head: ListNode) -> bool:
    q = collections.deque()
 
    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.popleft() != q.pop():
            return False
 
    return True
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(2)
list4 = ListNode(1)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
 
print(is_palindrome(head))

 

3. 러너를 통한 우아한 풀이

from typing import List
import collections
 
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None
 
def is_palindrome(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:
        slow, rev = slow.next, rev.next
    return not rev
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(2)
list4 = ListNode(1)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
 
print(is_palindrome(head))