234.回文链表

题目：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路：

回文链表从前往后和从后往前读到的结果相同，第一种办法是使用数组来存储整个链表的内容，如果正着和反着的数组相同，那么就是回文链表。第二种办法是使用快慢指针来查找当前指针的中间位置，将后半部分的指针进行反转，如果后半部分指针的值和前半部分的指针的值相等就认为是回文链表。指针反转可以参考206的反转链表

代码1：

class Solution:
    def isPalindrome(self, head) -> bool:
        if not head:
            return True
        p = head
        out = []
        while p:
            out.append(p.val)
            p = p.next
        if out!=out[::-1]:
            return False
        return True

时间复杂度：O(n)
空间复杂度：O(n)

代码2：

class Solution:
    def isPalindrome(self, head) -> bool:
        if not head or not head.next :
            return True 
        p = head
        q = head
        while q.next and q.next.next:
            p = p.next
            q = q.next.next
        prev = None
        current = p.next
        while current:
            next = current.next
            current.next = prev
            prev = current
            current = next
        first = head
        second = prev
        while second:
            if first.val!=second.val:
                return False
            first = first.next
            second = second.next
        return True