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 = Nonecur = head while cur:tmp = cur.next cur.next = prepre = curcur = tmpreturn pre def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if not head:return Trueslow = fast = head while fast.next and fast.next.next:fast = fast.next.nextslow = slow.next mid = self.reverse(slow.next)while mid:if head.val != mid.val:return Falsehead = head.next mid = mid.nextreturn True