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

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

13. 팰린드롬 연결 리스트

리트코드 234. Palindrome Linked List 문제입니다.

 

 

풀이

 문제 난이도는 easy 이지만, 연결 리스트에 대한 이해도가 부족하면 풀이 방법을 떠올리기 어렵습니다.

 책에서는 두 가지 풀이방법을 제시합니다.

 첫 번째는 연결 리스트를 리스트로 바꿔서 펠린드롬을 확인하는 풀이입니다.

 두 번째는 연결 리스트의 중앙값을 기준으로 역순 연결 리스트를 만들고 값을 비교하는 풀이입니다.

 

# 1. 리스트 변환
def isPalindrome(self, head):
    q = collections.deque()
    node = head
    while node:
        q.append(node.val)
        node = node.next

    while len(q) > 1:
        if q.popleft() != q.pop():
            return False
    return True
    
# 2. 역순 연결리스트 생성
def isPalindrome(self,head):
    slow, fast = self.head
    rev = None

    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
    if fast:
        rev = rev.next
    while rev and rev.val == slow.val:
        rev, slow = rev.next, slow.next
    return not rev