题目描述
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解法
若要满足 O(1) 空间复杂度，则不能借助于列表或栈结构存储数据。因为单链表不像字符串可以进行直接访问，所以这里采用的方式为，找到单链表中间元素，并反转单链表前半部分，然后与单链表后半部分进行比较是否为回文结构。
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow,fast,left=head,head,None
while fast and fast.next:
fast=fast.next.next
slow.next,left,slow=left,slow,slow.next
if fast:
slow=slow.next
while slow and slow.val==left.val:
slow,left=slow.next,left.next
return not slow
以 left 表示反转后单链表前半部分的头结点，第一个 while 循环中找到链表中间节点，并逐步反转链表节点，查找中间节点的方式为快慢两个指针，当快指针为空时，慢指针指向中间节点。第一个循环结束后，left 为前半部分反转链表的头结点，slow 为后半部分链表的头结点，因为链表中节点个数为奇数时，slow 为中心节点，不需要参与回文判断，所以第一个循环后，加 if 判断。第二个循环中判断 left 和 slow 两个链表的数据值是否一致。
此处采用反转链表的方式，会修改原链表的结构，因为记录了 left 和 slow 指针，所以可以在判断回文结构后进行恢复，此处不再赘述。
