[Algorithm] LeetCode #234 - Palindrome Linked List
개요
LeetCode #234, Palindrome Linked List 문제를 풀어봅니다.
Given the head of a singly linked list, return true if it is a palindrome.
Example 1:
Input: head = [1,2,2,1] Output: true
Example 2:
Input: head = [1,2] Output: false
Constraints:
- The number of nodes in the list is in the range
[1, 105]. 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
ListNode(linked list)에서 value를 뽑아서 리스트에 넣어 리스트로 바꾸고 pop으로 비교하는 방법이 있고, 리스트 대신 데크로 바꾸어 같은 일을 하는 방법이 있습니다. 리스트로 바꾸고 pop을 하면 한 칸씩 모든 값이 옮겨지면서 O(n)이 되고, 데크로 하면 O(1)이라 데크가 유리하다고 합니다.
import collections
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
q = []
if not head:
return True
# ListNode(linked list): Head -> value/next -> value/next -> ...
node = head
# covert to list
while node is not None:
q.append(node.val)
node = node.next
# palindrome?
while len(q) > 1:
if q.pop(0) != q.pop():
return False
return True
def isPalindrome_ver2(self, head: ListNode) -> bool:
# deque
q = collections.deque()
if not head:
return True
# ListNode(linked list): Head -> value/next -> value/next -> ...
node = head
# covert to list
while node is not None:
q.append(node.val)
node = node.next
# palindrome?
while len(q) > 1:
# deque is faster than linked list -> list
if q.popleft() != q.pop():
return False
return True
