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

Palindrome Linked List - LeetCode

나의코드

def isPalindrome(self, head: Optional[ListNode]) -> bool:
    l=[]
    # 리스트로 변환
    while head:
        l.append(head.val)
        head=head.next
    left,right=0,len(l)-1

    #팰린드롬 확인
    while left<=right:
        if l[left]!=l[right]:
            return False
        left+=1
        right-=1
    return True

연결리스트를 리스트로 변환한 뒤 투포인터를 이용하여 팰린드롬을 확인하였다.

리스트변환

def isPalindrome(self, head: Optional[ListNode]) -> bool:
    q=[]

    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

리스트로 변환한 것은 동일 하나 투포인터 대신 pop을 사용하여 더욱 직관적으로 풀이하였다. 그러나 pop(0)의 경우 O(n)의 시간복잡도가 소요된다. 

데크를 이용한 최적화

def isPalindrome(self, head: Optional[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

deque를 사용하면 O(1) 상수 시간만에 pop(0)과 동일한 동작을 하게된다.

런너를 이용한 우아한 풀이

def isPalindrome(self, head: Optional[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

    # 팰린드롬이 아니라면 rev == True, 맞다면 rev==False
    return not rev

연결 리스트를 리스트로 변환하지 않고 연결리스트의 자료형을 그래도로 유지한 풀이이다. 빠른런너와 느린런너 두명의 런너를 설정하고 빠른 런너는 2칸씩, 느린러너는 1칸씩 이동하게 하여, 빠른 런너가 끝에 도착하면 느린런너가 중앙에 도착하도록 한 방법이다. 

느린런너가 중앙으로 이동하면서 rev에 역으로 값을 저장하고 이를 중앙 이후 느린런너와 rev 값을 비교하며 팰린드롬인지 확인하는 방식이다.