234. 回文链表

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

解法一：

把链表的结点值全部存到list里面，然后比较list是否回文即可。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        return vals == vals[::-1]

解法二：

先找中点，然后原链封尾，并从中点开始到末尾，用头插法插入构建新链，若新链与原链相等说明是回文链

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:   #空链或只有一个节点
            return True
        if not head.next.next:   #只有两个结点
            return head.val == head.next.val
        
        Head = ListNode(0)  #辅助头
        Head.next = head
        fast = slow = Head
        while fast.next and fast.next.next:     #快慢指针找中点
            fast = fast.next.next
            slow = slow.next
        #从中点拆出新链
        newHead = ListNode(0)
        if fast.next:    #链长为奇数
            j = slow.next.next
            slow.next = None    #原链封尾
        else:   #链长为偶数
            j = slow.next
            slow.next = None    #原链封尾
        while j:    #头插法构建新链
            tmp = j
            j = j.next
            tmp.next = newHead.next
            newHead.next = tmp
        #比较两链是否相等
        while Head and newHead:
            if Head.val != newHead.val:
                return False
            Head = Head.next
            newHead = newHead.next
        return True