234. Palindrome Linked List
這一題是一道簡單的題目，可是其實很容易不小心踩到雷。第一個直覺的想法會是我們就把 Linked List 反轉，接著比較一下是不是都一樣就好。可是如果我們要反轉 Linked List ，第一件要做的事情會是我們要先複製一個原先的 Linked List ，不然 Linked List 都是傳指標，反轉完原先的 Linked List 就沒了。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def cloneLinkedList(self, head) -> ListNode:
copy = copy_head = ListNode(0)
curr = head
while curr:
copy.next = ListNode(curr.val)
copy = copy.next
curr = curr.next
return copy_head.next
def reverseList(self, head: ListNode) -> ListNode:
node = None
while head:
tmp = head.next
head.next = node
node = head
head = tmp
return node
def isPalindrome(self, head: ListNode) -> bool:
cloned = self.reverseList(self.cloneLinkedList(head))
curr = head
while curr:
if curr.val != cloned.val:
return False
curr = curr.next
cloned = cloned.next
return True
不過這一題其實存在著更優的解法，雖然理論時間複雜度並沒有真的改變非常多，可是少使用了很多的記憶體。
回文的題目的特性之一，就是前後對稱，所以我們其實並不用比對到整個 Linked List ，只要比對到一半就好，可是 Linked List 並沒有長度的概念，所以可以利用快慢指針的方式，取得 Linked List 的中間點（876. Middle of the Linked List）
第二步就是我們從中間點到結尾的部分，反轉整個 Linked List ，這樣的話我們就會有兩個「幾乎」一模一樣的 Linked List，接下來和上面的部分一樣，一起齊步走，如果中間有一個位置發生不同的值，那就不是回文。
如果有看到「幾乎」不一樣的地方的話，就要注意了，回文有另外一個特性，在每個題目裡面我們都要注意，那就是回文的長度是奇數還是偶數，這裡要注意的只有奇數個個數的回文，在我們找中點的時候，後半部的元素其實是會多一的長度，可是我們在檢查得時候需不需要注意呢？是不需要的，因為在反轉 Linked List 時，這個最中間的元素，會到最後面，每個元素都檢查完的時候，雖然說只會剩下這個元素沒有被檢查到，但是因為只有一個元素，也符合回文的特性，所以不檢查也沒關係，程式就不需要特別額外的去判斷。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# 206. Reverse Linked List
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while head:
tmp = head.next
head.next = prev
prev = head
head = tmp
return prev
# 876. Middle of the Linked List
def middleNode(self, head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def isPalindrome(self, head: ListNode) -> bool:
mid = self.middleNode(head)
node = self.reverseList(mid)
while node:
if node.val != head.val:
return False
node = node.next
head = head.next
return True