每日leetcode——234. 回文链表数据结构与算法

题目给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

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

思路第一个想到的就是，直接把整个链表翻转，然后和原来的链表比较。
但是题目要求时间复杂度O(n)，空间复杂度O(1)，这个思路要保存翻转后的链表，空间复杂度首先就不满足了。
【每日leetcode——234. 回文链表】满足复杂度的思路如下：

将链表从中间一分为二
使用快慢指针，slow每次移动1个节点，fast每次移动2个节点。当fast移动到末尾，无法继续前进2个节点时，slow所在的节点就是链表的中间位置。
将右半部分链表翻转
遍历左、右两个链表的每个节点，看每个节点的值是否相同

def isPalindrome(self, head: ListNode) -> bool: # 初始化快慢指针 slow = fast = head# 遍历链表，移动快慢指针，切分链表 # 当fast移动到尾节点或尾节点的前一个节点时，下一次无法移动2个节点，则遍历完成 # 此时slow指针指向了链表的中间位置 while fast.next and fast.next.next: slow = slow.next fast = fast.next.next# 翻转右半部分链表 # 在翻转后的右半部分链表头节点设置rightHead指针 rightHead = self.reverseList(slow.next)# 在左半部分链表头节点设置leftHead指针 leftHead = head# 以遍历右半部分链表为准，因为切分链表的时候，如果链表节点个数是奇数，左半部分会多1个节点 while rightHead: # 如果有节点的值不同，就不是回文链表，返回False if leftHead.val != rightHead.val: return False # 移动指针 leftHead = leftHead.next rightHead = rightHead.next# 遍历结束，节点的值都相同，是回文链表，返回True return Truedef reverseList(self,head): if head==None or head.next==None: return headtmp = self.reverseList(head.next) head.next.next = head head.next = Nonereturn tmp