编写 Python 程序检查给定链表是否为回文

在本教程中，我们将编写一个Python程序来检查给定的链表是否为回文。链表是一种在计算机编程中用于存储和组织元素集合的数据结构。它由一系列节点组成，每个节点存储一个数据元素和一个指向序列中下一个节点的引用（或指针）。

与数组不同，链表的节点不存储在连续的内存位置中。相反，每个节点在内存中独立分配，并通过引用或指针连接到下一个节点。这使得在链表中添加或删除元素变得容易，因为我们只需要更新节点的引用字段即可反映更改。

解决方案

首先，我们将使用栈来解决这个问题。让我们理解下面的例子。

示例 -

输出

True

解释 -

上面的程序使用栈来检查给定的链表是否为回文。我们首先定义一个Node类来表示链表的单个节点。is_palindrome()函数以链表的头节点作为输入，如果链表是回文则返回True，否则返回False。

我们首先处理链表为空或只有一个节点的情况，因为这样的链表始终是回文。

然后，我们使用快慢指针找到链表的中间节点。我们遍历链表，快指针的速度是慢指针的两倍。当快指针到达链表末尾时，慢指针指向链表的中间。

然后，我们将链表的前半部分压入栈中。我们从头节点开始遍历链表的前半部分，并将节点的数??据元素压入栈中。

然后，我们将链表的后半部分与栈进行比较。如果链表中的节点数量为奇数，我们从中间节点的下一个节点开始比较。

否则，我们从中间节点本身开始比较。我们使用一个名为curr的指针，从上述确定的节点开始遍历链表的后半部分，并将节点的数据元素与从栈中弹出的元素进行比较。如果我们发现两个半部分中对应节点之间有任何不匹配，我们就知道链表不是回文，并返回False。

否则，如果我们到达后半部分的末尾而没有发现任何不匹配，我们就知道链表是回文，并返回True。

示例 - 2

输出

True

解释 -

上面的代码定义了一个具有data和next属性的Node类，以及一个名为is_palindrome()的函数，该函数接受由其头节点表示的链表作为参数，并返回True，如果链表是回文，即从头到尾的节点序列与从尾到头的节点序列相同，否则返回False。

is_palindrome()函数首先检查给定的链表是否为空或仅包含一个节点，在这种情况下，它显然是一个回文，并返回True。

否则，它使用快慢指针技术找到链表的中间节点，并通过修改节点的next指针来反转链表的后半部分。

最后，它比较链表前半部分的节点数据值和反转后的后半部分节点的数??据值，如果它们都匹配则返回True，否则返回False。

在示例代码中，创建了一个包含节点值1、2、3、2、1的链表，并调用is_palindrome()函数，将链表的头节点作为参数传递。由于链表是回文，函数返回True，并在控制台打印出来。

时间复杂度： O(n)，其中n表示给定链表的长度。

结论

本教程介绍了如何查找回文链表。我们已经使用两种方法解决了这个问题。在第一种方法中，我们使用了栈，在第二种方法中，我们遍历链表并检查链表是否为回文。