题解 | #判断一个链表是否为回文结构#

这道题的难点在于用O(1)的space.解决方案是将链表的第二部分就地反转，再跟第一部分逐个比较。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head ):
        # write code here
        def reverseList(head):
            prev, curr, nxt = None, head, head
            while curr:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
            return prev
        if not head or not head.next:
            return True
        dummy = ListNode(0)
        dummy.next = head
        slow, fast = dummy, dummy
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        secondHalf = slow.next
        slow.next = None
        reversedSecondHalf = reverseList(secondHalf)
        p1, p2 = head, reversedSecondHalf
        while p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        return True