LEETCODE - Palindrome Linked List
コレクションの使用
from typing import List, Deque
import collections
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalidrome(self, 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(): # pop(0) 맨 앞, pop() 맨 뒤
return False
# 연결 리스트에서 pop(0)을 하면 모든 값이 한 칸씩 shifting되며 시간 복잡도 O(n)이 발생한다.
# Deque는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)에 실해된다.
def isPalidrome_deque(self, 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
Runnerテクノロジーの使用
def isPalindrome_runner(self, head: 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
Reference
この問題について(LEETCODE - Palindrome Linked List), 我々は、より多くの情報をここで見つけました https://velog.io/@aspalt85/LEETCODE-Palindrome-Linked-Listテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol