[연결 리스트] 팰린드롬 연결 리스트

* leetcode 234. Palindrome Linked List

 

Q. 연결리스트가 팰린드롬 구조인지 판별하라.

# 입력
1->2

# 출력
false

# 입력
1->2->2->1

# 출력
true

---

풀이 1. 리스트 변환

# 연결 리스트를 파이썬의 리스트로 변환시켜 풀이
def isPalindrome(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

 

풀이 2. 데크를 이용한 최적화

# 코드를 최적화하기 위해 데크를 활용한다.
# 동적 배열로 구성된 리스트는 맨 앞 아이템을 가져오면 모든 값이 하나씩 시프팅되어 시간 복잡도가 O(n)이 발생한다.
# 하지만, 데크를 활용하면 시간 복잡도 O(1)로 처리를 끝낼 수 있다.
# 위 코드와의 차이는 데크를 선언하는 코드와 pop(0) 대신 popleft()로 처음 값을 뽑는 코드 2곳 뿐이다.

def isPalindrome(head: ListNode) -> bool:
    q: Deque = 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

 

풀이 3. Runner를 이용한 우아한 풀이

# 입력 1->2->3->2->1

def isPalindrome(head: LinkNode) -> bool:
    rev = None
    slow = fast = head
    
    # 런너를 이용해 역순 연결 리스트 구성
    while fask and fask.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
        # 1차
        # fast : 3
        # rev  : 1->None
        # slow : 2->3->2->1
        
        # 2차
        # fast : 1
        # rev  : 2->1->None
        # slow : 3->2->1
        
        # 3차
        # fast.next가 없으니 끝
        
    if fast:
        slow = slow.next
        
        # fast : 1
        # rev  : 2->1->None
        # slow : 2->1
        
    # 팰린드롬 여부 확인
    while rev and rev.val == slow.val:
        slow, rev = slow.next, rev.next
    
    return not rev