1 minute read

234. Palindrome Linked List

문제 링크

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

문제 설명

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

제한 사항

  • The number of nodes in the list is in the range [1, 105].
  • 0 <= Node.val <= 9

입출력 예 #1

  1. Input: head = [1,2,2,1]
  2. Output: true

입출력 예 #2

  1. Input: head = [1,2]
  2. Output: false

문제 풀이

  1. 리스트로 형변환 하여 풀이 : 리스트의 pop(0), pop() 메소드를 이용하여 풀이
  2. 데크를 이용한 최적화 풀이 : 리스트의 pop(0)을 사용하면 O(N)의 시간 복잡도가 소요됨, 따라서 리스트의 양끝을 O(1)의 시간복잡도를 가진 Deque를 사용
  3. 런너 기법을 이용한 풀이 : 연결 리스트를 1번씩 가는 slow, 2번씩 가는 fast를 이용하면 fast가 리스트 순회를 마칠 때는 slow가 중앙에 있는 점을 착안하여 풀이
## 리스트로 형변환 하여 풀이
class Solution:
    def isPalindrome(self, head: Optional[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

## 데크를 이용한 최적화 풀이
class Solution:
    def isPalindrome(self, head: Optional[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

## 런너 기법을 사용한 풀이
class Solution:
    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
        return not rev

Comments

You May Also Enjoy