面试题02.06.回文链表.md

面试题 02.06. 回文链表

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

示例 1：

输入： 1->2
输出： false 

示例 2：

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

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

解题思路

快慢指针+哑节点

1. 快慢指针遍历到链表中间，快指针走两步、慢指针走一步，最后慢指针的位置就是链表中间（画个示例图就知道了，虽然我这看的是该题的评论，不太明白，然后画了个图就了解了）
2. 从中间开始反转链表后半段
3. 从原链表头和反转后的链表头开始比较 value

代码

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


class Solution(object):
    def get_middle(self, head):
        """用快慢指针获取中间节点"""
        left = right = head
        while right and right.next:
            left = left.next
            right = right.next.next
        return left

    def reverse_link(self, head):
        """反转链表"""
        cur = head
        pre = None
        while cur:
            after = cur.next
            cur.next = pre
            pre = cur
            cur = after
        return pre

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None:
            return True
        # 获取中间节点
        middle_node = self.get_middle(head)

        # 反转链表
        first = head
        second = self.reverse_link(middle_node)
        while second:
            if first.val != second.val:
                return False
            first = first.next
            second = second.next
        return True