关于leetcode:完虐算法判断一个链表是否为回文结构

判断一个链表是否为回文结构

更多算法题解，请关注公众号【程序员学长】

问题形容

LeetCode 剑指 Offer II 027. 回文链表

给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。

示例：

输出：{1,2,2,1}

输入：true

阐明：1 -> 2 -> 2 -> 1

剖析问题

回文串是斧正读反读都一样的字符串，最简略的是应用双指针法。然而对于链表这种数据结构来说，指针只能向一个方向挪动，也就是说只能找到后继节点，没方法找到前驱节点。所以没方法应用双指针法，要想应用双指针，咱们就须要把链表元素放入一个数组中，而后再去判断是否是回文，这须要 O（n）的空间复杂度，这里就不在赘述。大家能够去看第 44 题。

咱们能够这么思考，将链表的后半局部进行反转，而后将前半部分和后半局部进行比拟，如果雷同就代表是回文链表，否则不是回文链表。寻找链表的中点咱们能够应用快慢指针的形式。

1. 快慢指针寻找链表中点。

2. 对链表的后半局部进行翻转

3. 前半部分和后半局部进行比拟。

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