題目出處
難度
easy
個人範例程式碼 – Deque (比較進階)，空間 O(N)
# 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: Optional[ListNode]) -> bool:
if not head:
return False
dq = deque([])
while(head):
dq.append(head.val)
head = head.next
return self.is_palindrome(dq)
def is_palindrome(self, dq):
while(len(dq)>=2):
if dq.popleft() == dq.pop():
continue
else:
return False
else: # if len(dq) == 1, True or len(dq) == 0, True
return True
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
Deque 解 palindrome 的題目真的是無敵，但因為是比較進階的資料結構，也許不一定是面試想要看到的解
input handling
處理沒有 head 的情況，return False
Boundary conditions
控制 pointer 搜尋至 None
個人範例程式碼 – 同向 two pointer, 使用空間 O(N/2) stack
# 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: Optional[ListNode]) -> bool:
if not head:
return False
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
else:
if not fast:
return self.odd_case(head, slow, fast)
else: # not fast
return self.even_case(head, slow, fast)
def odd_case(self, head, slow, fast):
mid = slow
stack = deque([])
slow = slow.next
while(slow):
stack.append(slow.val)
slow = slow.next
# print(stack)
while(stack):
if head.val == stack.pop():
head = head.next
else:
return False
else:
return True
def even_case(self, head, slow, fast):
mid = slow
stack = deque([])
slow = slow.next
while(slow):
stack.append(slow.val)
slow = slow.next
# print(stack)
while(stack):
if head.val == stack.pop():
head = head.next
else:
return False
else:
return True
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
我猜此題目最多會要求到把使用空間壓縮至 O(1)，
這樣上面 Deque 的做法會因為空間 O(n) 而不能用。
如果要實現 O(1) 空間的話，
這題就可以考到 LinkedList 的反轉，同向 two pointer。
不過這邊求速度，就先不寫 LinkedList 的反轉，
使用 O(N/2) 空間的 stack 完成同樣的任務
input handling
處理沒有 head 的情況，return False
Boundary conditions
控制 slow, fast pointer 搜尋至 None，
注意結束條件的 fast and fast.next
個人範例程式碼 – 同向 two pointer，使用 reverse LinkedList 空間 O(1)
# 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: Optional[ListNode]) -> bool:
if not head:
return False
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
else:
if not fast:
return self.odd_case(head, slow, fast)
else: # not fast
return self.even_case(head, slow, fast)
def odd_case(self, head, slow, fast):
dummy = self.reverse(slow)
while dummy:
# print(dummy.val, head.val)
if dummy.val == head.val:
head, dummy = head.next, dummy.next
else:
return False
return True
def even_case(self, head, slow, fast):
dummy = self.reverse(slow.next)
while dummy:
# print(dummy.val, head.val)
if dummy.val == head.val:
head, dummy = head.next