判断一个链表是否为回文结构
更多算法题解，请关注公众号【程序员学长】
问题形容
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