【完虐算法】判断一个链表是否为回文结构【完虐算法】判断一个链表是

判断一个链表是否为回文结构更多算法题解，请关注公众号【程序员学长】
问题描述
LeetCode 剑指 Offer II 027. 回文链表
给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。
示例：
输入：{1,2,2,1}
输出：true
说明：1 -> 2 -> 2 -> 1
分析问题
回文串是指正读反读都一样的字符串，最简单的是使用双指针法。但是对于链表这种数据结构来说，指针只能向一个方向移动，也就是说只能找到后继节点，没办法找到前驱节点。所以没办法使用双指针法，要想使用双指针，我们就需要把链表元素放入一个数组中，然后再去判断是否是回文，这需要O（n）的空间复杂度，这里就不在赘述。大家可以去看第44题。
我们可以这么考虑，将链表的后半部分进行反转，然后将前半部分和后半部分进行比较，如果相同就代表是回文链表，否则不是回文链表。寻找链表的中点我们可以使用快慢指针的方式。

快慢指针寻找链表中点。

文章图片

对链表的后半部分进行翻转

文章图片

前半部分和后半部分进行比较。

【【完虐算法】判断一个链表是否为回文结构】

文章图片

class Solution: def isPalindrome(self, head) -> bool: #链表为空，直接返回true if head is None: return True#找到链表的中点 middle_point = self.middle_point(head) second_start = self.reverse_list(middle_point.next)#判断前半部分和后半部分是否相等 result = True first = head second = second_start while result and second is not None: if first.val != second.val: result = False first = first.next second = second.next#还原链表并返回结果 middle_point.next = self.reverse_list(second_start) return result#快慢指针寻找中点 def middle_point(self, head): fast = head slow = head while fast.next is not None and fast.next.next is not None: fast = fast.next.next slow = slow.next return slow#翻转链表 def reverse_list(self, head): previous = None current = head while current is not None: next_node = current.next current.next = previous previous = current current = next_node return previous