面试题 02.06. 回文链表

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

示例 1：

输入： 1->2
输出： false

示例 2：

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

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

Python 解答：
1.存储判断

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        res = []
        while head:
            res.append(head.val)
            head = head.next
        i, j = 0, len(res)-1
        while i < j:
            if res[i] == res[j]:
                i += 1
                j -= 1
            else:
                return False
        return True

2.递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        self.p = head
        def isHelper(q):
            res = True
            if q != None:
                res = isHelper(q.next)
                res = res and (self.p.val == q.val)
                self.p = self.p.next
            return res
        return isHelper(head)

3.反转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        def travese(head):
            first = head
            last = None
            while first:
                temp = first
                first = first.next
                temp.next = last
                last = temp
            return last
        p, q = head, head
        while p != None and p.next != None:
            p = p.next.next
            q = q.next
        if p:
            q = q.next
        q = travese(q)
        while q:
            if q.val != head.val:
                return False
            q = q.next
            head = head.next
        return  True