题目：

请判断一个链表是否为回文链表。

示例：

输入: 1->2->2->1
输出: true

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

思路：

方法1

遍历链表，将节点的值放在数组中，然后判断数组是不是回文的。这里将节点的值放在列表中，最后返回列表反转是否和原来相等的逻辑值。也可以使用双指针来判断列表是否是回文的。

方法2

先将链表使用快慢指针分成两部分，节点个数是奇数或者偶数都可以，然后反转后半部分链表，再比较两段链表是否相等，在返回结果之前再将后半部分链表反转回来。保持不改变原来的链表。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # 空间和时间复杂度都是O(n)
        # vals = []
        # while head:
        #     vals.append(head.val)
        #     head = head.next
        # return vals == vals[::-1]
        #空间复杂度为O(1)解法
        #步骤：分成前后两断，反转后面一段，判断两段是否相等，后面反转回来，返回结果
        # res = True
        slow = fast = head 
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        revhead = self.reverlist(slow)
        p1 = head
        p2 = revhead
        while p1 and p2:
            if p1.val != p2.val:
                slow.next = self.reverlist(revhead)
                return False
            p1 = p1.next
            p2 = p2.next
        slow.next = self.reverlist(revhead)
        return True
    def reverlist(self,node):
        pre = None
        while node:
            temp = node.next
            node.next = pre
            pre = node
            node = temp
        return pre