Leetcode 234. 回文链表

题目描述

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

示例 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 指针，所以可以在判断回文结构后进行恢复，此处不再赘述。