回文链表_

编写一个函数，检查输入的链表是否是回文的。

示例 1：

输入： 1->2
输出： false 

示例 2：

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

示例代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res == res[::-1]

复杂度分析:

时间复杂度：O(n)，其中 n 指的是链表的元素个数。 第一步： 遍历链表并将值复制到数组中，O(n)。 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。 总的时间复杂度：O(2n) = O(n)。 空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

示例代码2：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return True
        slow = head
        fast = head

        # slow 遍历到中间，最后 slow 停的位置是 n/2+1
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 然后从 slow 开始反转链表
        # 如果是奇数，多出来的一个节点不用管了
        pre = slow
        while slow and slow.next:
            tmp = slow.next.next
            slow.next.next = pre
            pre = slow.next
            slow.next = tmp
        
        # 反转后的头结点是 pre，从 pre 和 head 开始比较 val
        while pre and head:
            if pre.val != head.val:
                return False
            pre = pre.next
            head = head.next
        return True

解题思路：

1. 快慢指针遍历到链表中间，快指针走两步、慢指针走一步，最后慢指针的位置就是链表中间
2. 从中间开始反转链表后半段
3. 从原链表头和反转后的链表头开始比较 value