[파이썬 알고리즘] 8장 - 팰린드롬 연결 리스트 (leetcode 234)

https://leetcode.com/problems/palindrome-linked-list/

Palindrome Linked List - LeetCode

 

<문제>

Given a singly linked list, determine if it is a palindrome.

 

<예시>

Input: 1->2

Output: false

 

Input: 1->2->2->1

Output: true

 

 

 

---

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

 

def isPalindrome(head: ListNode) -> bool:
    deq = deque()
    # 양방향에서 삽입/삭제할 수 있는 자료구조
    # Q. 왜 list 대신 deq를 사용하면 성능이 향상되는가?
    # A. list에서 가장 앞에 위치한 원소를 pop하면 shift가 일어나며 O(n) 소요
    #    반면, deque는 가장 앞에 위치한 원소 pop하면 O(1)

    # 1. linked list의 모든 원소를 deque로 옮긴다
    node = head
    while node != None:
        deq.append(node.val) # 끝에 삽입
        node = node.next

    # 2. 양방향에서 pop하며 동일하지 않다면 그 즉시 False return
    while len(deq) > 1:
        # 입력으로 받는 node의 개수가 홀수/짝수인 경우 모두 고려하기 위해
        # len(deq) > 1 이면 loop를 돌도록 코드 작성
        right_val = deq.pop()
        left_val = deq.popleft()
        if right_val != left_val:
            return False
    return True

리스트를 사용하여 linked list를 저장할 수 있지만, deque를 사용하는 것이 성능향상에 도움이 된다.

그 이유는 리스트의 경우 앞에 위치한 원소를 제거할 경우 shifting이 발생하여 O(n)이 소요되지만,

deque는 양쪽에서 삽입/삭제할 수 있는 자료형으로, 앞에 위치한 원소를 제거해도 O(1)밖에 소요되지 않는다.

따라서 리스트보다는 deque를 사용하는 게 성능 향상에 도움이 된다.

 

 

 

파이썬 알고리즘 인터뷰 책에서는 runner를 활용한 풀이를 제시하였다.

def runner_solution(head: ListNode) -> bool:
    # 1. slow runner, fast runner head로 초기화
    slow, fast = head, head
    rev = None # reversed linked list

    # reversed linked list 구성
    while fast and fast.next:
        # 여기서 fast runner는 linked list의 절반 지점을 체크하기 위하여 사용
        fast = fast.next.next  # 2 step 이동
        rev, rev.next, slow = slow, rev, slow.next # reversed linked list 구성

    if fast:
        slow = slow.next  # 홀수 길이의 linked list 받은 경우를 위해

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

linked list의 경우 순차접근만 가능하기 때문에 따로 길이를 저장하지 않으면, 어디가 중간인 지 알 수 없다.

따라서 fast runner, slow runner 개념을 도입하였다.

 

slow runner는 1 step씩, fast runner는 2 step씩 이동하기 때문에 fast runner가 linked list의 끝 지점에 도달한 경우 slow runner는 중간 지점에 도달한다. 따라서 linked list의 중간 지점에 도달한 순간을 알 수 있게 되는 것이다.

 

위의 풀이에서는 절반 지점에 대응되는 reversed linked list를 만들어 팰린드롬 여부를 확인한다.

예를 들어 1->2->3->4->3->2->1 이라는 linked list가 존재한다면

reversed linked list로는 3->2->1 이 만들어진다. (4은 중간에 위치하므로 제외된다)

이렇게 만들어진 reversed linked list와 1->2->3->4->3->2->1의 초록색 부분을 비교하며 팰린드롬인 지 확인한다.