嗨，我正在嘗試從 leetcode 解決回文鏈表問題。我已經提出了一個解決方案，但我不確定它為什么不正確。如果有人可以向我解釋我的誤解，我將不勝感激。
問題：給定單鏈表的頭部，如果是回文則回傳真，否則回傳假。完整的描述可以在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]，我的解決方案未通過測驗。我的輸出是真的，但預期的輸出是假的。
我認為我在理解頭和節點概念方面有問題？頭只是鏈表的第一個節點，對嗎？在這種情況下，第一個節點/頭將是 1？
在詢問之前我嘗試自行除錯，但 pycharm 回傳一個我不明白的錯誤。如何使用 [1, 1, 2, 1] 作為解決方案的輸入？
q = Solution()
print(q.isPalindrome(ListNode(1, 1)))
reversedhead = reversedhead.next
AttributeError: 'int' object has no attribute 'next'
uj5u.com熱心網友回復：
您的想法似乎如下：
- 反轉串列
- 沿著串列向前走，同時沿著反向串列向后走
- 如果每個比較值都相同，則為回文
邏輯錯誤出現在第 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' object has no attribute 'val' inlinked list LeetCode challenge的回答，了解如何做到這一點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514859.html
標籤：Python算法链表
下一篇：使用二維陣列尋找孤立的城市