问题描述
我正在寻找234. Palindrome Linked List的解决方案:
给定单链表的head,如果它是回文,则返回true。
这是正确的解决方案:
class Solution: def isPalindrome(self, head: ListNode) -> bool: #Null condition if head == None: return True #move fast and slow pointers s_p = head f_p = head while(f_p.next != None and f_p.next.next != None): s_p = s_p.next f_p = f_p.next.next #reverse slow pointer first_half = self.reverse(s_p) #compare while(first_half != None and head != None): print(first_half.val) print(head.val) if(first_half.val != head.val): return False first_half = first_half.next head = head.next return True def reverse(self,c_p): prev_head = None while(c_p != None): temp = c_p.next c_p.next = prev_head prev_head = c_p c_p = temp return prev_head
但我很难理解该代码为什么会起作用。
示例:1->;2-->;1
根据这个YouTube video的想法是,我们取列表的前半部分,将其颠倒过来,然后进行比较。
该插图显示,我们将在反转后将指向1-&>2;->Null的指针与另一个为1-&>Null的指针进行比较。
虽然在我看来,这实际上是将上半年:1-&>;2->Null与 Head:1->;2->;空。此代码确实通过了所有测试用例,但我预计第二个代码(我的修改版本)也应该可以工作,但它不能:
class Solution: def isPalindrome(self, head: ListNode) -> bool: #Null condition if head == None: return True #move fast and slow pointers s_p = head f_p = head while(f_p.next != None and f_p.next.next != None): s_p = s_p.next f_p = f_p.next.next #set s_p.next to Null s_p.next = None #reverse fast pointer second_half = self.reverse(f_p) #compare while(second_half != None and head != None): print(second_half.val) print(head.val) if(second_half.val != head.val): return False second_half = second_half.next head = head.next return True def reverse(self,c_p): prev_head = None while(c_p != None): temp = c_p.next c_p.next = prev_head prev_head = c_p c_p = temp return prev_head
这样,我所要做的就是将第二个指针:2->1->Null反转为1-&>2-&>Null
现在我们可以将头部与反转的下半部进行比较。
它没有通过LeetCode中的测试,但我很困惑为什么不能。
我知道这是一个简单的问题,但我仍然在努力。
非常感谢您的帮助。
推荐答案
您修改的版本中有一个错误
您的逻辑是正确的,但是当您的反向函数被定义为从参数PASS反转列表时,f_p将指向最后一个元素,而不是中间元素。
Leetcode版本解决方案将起始值与反转后半部分的值进行比较。