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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

단일 연결 리스트의 팰린드롬 판별

 

책에서 구현된 코드

    def isPalindrome(self, head: ListNode) -> bool:
        rev = None
        slow = fast = head

        while fast and fast.next:
            fast = fast.next.next
            # 단일 연결리스트 reverse
            rev, rev.next, slow = slow, rev, slow.next
        if fast:
                slow = slow.next

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

 

기억해야할 기법

• Runner 기법
  
  • fast runner / slow runner 두 포인터를 사용하는 기법
  • 연결 리스트에서 한 포인터가 앞서게 하여 병합 지점 / 중간 위치 / 길이 등을 판별
• reverse list
  • 단일 연결 리스트를 순차탐색하면서 어렵지 않게 reverse할 수 있는 듯
  • rev, rev.next, slow = slow, rev, slow.next
    1. rev = slow
       - 현재 위치로 이동
    2. rev.next = rev
       - 이전 노드가 next
    3. slow = slow.next
       - 다음 탐색할 slow
       - 하나의 line이므로, 2번으로 인한 slow.next가 손상되지 않음

 

내가 구현한 코드

    def isPalindrome(self, head: ListNode) -> bool:
        q = deque()
        while head:
            q.append(head.val)
            head = head.next

        while len(q) > 1:
            if q.popleft() != q.pop():
                return False
        return True

• 내가 구현한 알고리즘

• 책에서 구현한 알고리즘

• 결과를 비교해보면 책에서 소개하는 내용이 공간복잡도도 줄이고, 탐색양도 줄이는 좋은 알고리즘인 것 같다
• 다중 할당의 활용이 낯설어서 제대로 활용할 수 있을지 모르겠다
  • 다중 할당을 제대로 사용하면 코드의 양이 짧아져서 가독성이 좋아질 것 같다
• 다중 할당의 사용
  • 변경되는 변수의 기존값을 활용하고 싶을 때
  • 변수 간의 양방 값의 교환이 필요할 때