LeetCode 234. 回文链表的算法解析

LeetCode 234. 回文链表的算法解析

引用

CSDN

1.

https://m.blog.csdn.net/weixin_44245188/article/details/143515836

本文将介绍如何判断一个单链表是否为回文链表的算法问题。通过将链表的值复制到数组列表中，然后使用双指针法判断是否为回文，最后给出具体的Python代码实现。

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

算法一共为两个步骤：

1. 复制链表值到数组列表中。
2. 使用双指针法判断是否为回文。

第一步，我们需要遍历链表将值复制到数组列表中。我们用 currentNode 指向当前节点。每次迭代向数组添加 currentNode.val，并更新 currentNode = currentNode.next，当 currentNode = null 时停止循环。

执行第二步的最佳方法取决于你使用的语言。在 Python 中，很容易构造一个列表的反向副本，也很容易比较两个列表。而在其他语言中，就没有那么简单。因此最好使用双指针法来检查是否为回文。我们在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，返回 false；相同则将两个指针向内移动，并继续判断，直到两个指针相遇。

在编码的过程中，注意我们比较的是节点值的大小，而不是节点本身。正确的比较方式是：node_1.val == node_2.val，而 node_1 == node_2 是错误的。

下面是具体的Python代码实现：

class Solution:  
    def isPalindrome(self, head: ListNode) -> bool:  
        vals = []  
        current_node = head  
        while current_node is not None:  
            vals.append(current_node.val)  
            current_node = current_node.next  
        return vals == vals[::-1]