回文链表Python解释

Question

嗨，我正在尝试解决leetcode中的回文链表问题。我已经提出了一个解决方案，但我不确定为什么它是不正确的。如果有人能向我解释我的误解，我将不胜感激。

问题：给定一个单链列表的头，如果它是回文，则返回true，否则返回false。完整描述可在https://leetcode.com/problems/palindrome-linked-list/

这是我的错误尝试(看起来有点像真正的解决方案(

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

class Solution:
# returns bool true or false
def isPalindrome(self, head):
# reverse the linked list
# define another same head for the reversion 
reversedhead = head
# Define a previous to invert the link
prev = None
# while head is not None
while reversedhead:
# temp variable
current = reversedhead
reversedhead = reversedhead.next
current.next = prev
prev = current
while head:
if prev.val != head.val:
return False
prev = prev.next
head = head.next
return True

这是我在网上找到的一个解决方案：

class Solution:
# returns bool true or false
def isPalindrome(self, head):
slow = head
# find the mid node
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# reverse the second half
node = None
while slow:
nxt = slow.next
slow.next = node
node = slow
slow = nxt
# compare the first and second half nodes
while node: # while node and head:
if node.val != head.val:
return False
node = node.next
head = head.next
return True

我的代码看起来有点相似，但它是错误的。while循环中我的语句的顺序与正确解决方案中语句的顺序不同。对于头部[1，1，2，1]，我的解决方案未通过测试。我的输出为true，但预期的输出为false。

我想我在理解头和节点概念方面有问题吗？头只是链表的第一个节点，对吗？在这种情况下，第一个节点/头将是1？

在询问之前，我试着自己调试，但pycharm返回了一个我不理解的错误。如何使用[1，1，2，1]作为解决方案的输入？

q = Solution()
print(q.isPalindrome(ListNode(1, 1)))
reversedhead = reversedhead.next
AttributeError: 'int' object has no attribute 'next'

Answer 1

您的想法似乎如下：

1. 反转列表
2. 沿着列表向前走，同时沿着反向列表向后走
3. 如果每个比较值都相同，那么它就是一个回文

逻辑错误出现在步骤2中：您不能再继续遍历列表，因为它已被反转。只有一个列表。head现在是该列表的尾部，因此head.next是None。因此，这个循环在第二次迭代中会遇到麻烦，因为此时head就是None。

第二个正确的算法只反转列表的后半部分，所以现在有可以以正向方式遍历的前半部分和可以以反向方式遍历的后半部分。这样，它确实会起作用。

或者，如果您在不更改原始链表节点的情况下克隆所有节点，并反向链接这些节点，您的想法也会奏效。显然，这将分配O(n(的内存，因此不如您已经引用的正确解决方案：优化

def isPalindrome(self, head: Optional[ListNode]) -> bool:
reversedhead = None
current = head
while current:
reversedhead = ListNode(current.val, reversedhead)
current = current.next
while head:
if reversedhead.val != head.val:
return False
reversedhead = reversedhead.next
head = head.next
return True

至于在本地环境中测试这一点：您不应该向函数传递列表，而应该传递ListNode的实例。虽然LeetCode在调用函数之前会为您做这件事，但在本地环境中，您必须自己准备输入。

查看我在AttributeError上的回答："list"对象在链表LeetCode中没有属性"val"，了解如何做到这一点。