Leetcode 234:回文链接列表
it1352
帮助15人
问题说明
我正在寻找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中的测试,但我很困惑为什么不能。
我知道这是一个简单的问题,但我仍然在努力。
非常感谢您的帮助。
正确答案
#1
您修改的版本中有一个错误
您的逻辑是正确的,但是当您的反向函数被定义为从参数PASS反转列表时,f_p将指向最后一个元素,而不是中间元素。
Leetcode版本解决方案将起始值与反转后半部分的值进行比较。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /reply/detail/tancce
系列文章
更多
同类精品
更多
-
YouTube API 不能在 iOS (iPhone/iPad) 工作,但在桌面浏览器工作正常?
it1352 07-30 -
iPhone,一张图像叠加到另一张图像上以创建要保存的新图像?(水印)
it1352 07-17 -
保持在后台运行的 iPhone 应用程序完全可操作
it1352 07-25 -
使用 iPhone 进行移动设备管理
it1352 07-23 -
在android同时打开手电筒和前置摄像头
it1352 09-28 -
扫描 NFC 标签时是否可以启动应用程序?
it1352 08-02 -
检查邮件是否发送成功
it1352 07-25 -
Android微调工具-删除当前选择
it1352 06-20 -
Android App 和三星 Galaxy S4 不兼容
it1352 07-20 -
希伯来语的空格句子标记化错误
it1352 06-22