leetcode-234. 回文链表

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

思路

快慢指针+反转链表

1）慢指针走一步，快指针走两步，找到中间结点

2）从中间结点开始进行反转链表

3）比对两个链表，如果值不一样，则返回false

ps：反转链表的时候，pre初始值设置成None，设置成-1会有问题，None利于3)的循环

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverse(self, head):
        pre = None
        cur = head 
        while cur:
            tmp = cur.next 
            cur.next = pre
            pre = cur
            cur = tmp
        return pre 

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return True
        slow = fast = head 
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next 
        mid = self.reverse(slow.next)
        while mid:
            if head.val != mid.val:
                return False
            head = head.next 
            mid = mid.next
        return True