我正在看《极客对极客的反向顺序合并2排序链表练习挑战》:
给定两个大小相同的链表 N
及 M
,按非降序排序。任务是以这样一种方式合并它们,即结果列表按降序排列。
输入:
输入的第一行包含测试用例的数量t。对于每个测试用例,输入的第一行分别表示链表n和m的长度[sic]。接下来的两行包含两个链表的n和m个元素。
输出:
对于每个测试用例,以非递增顺序打印合并的链表。
用户任务:
任务是完成该功能 mergeResult()
它引用两个链表的头并返回指向合并链表的指针。
我的方法
我试图先按升序合并列表,然后将其反转。它适用于大多数测试用例,但在少数情况下失败并出现错误:-
第21行,合并结果
p3=p3.next
attributeerror:“非类型”对象没有属性“下一个”
def mergeResult(h1,h2):
p1=h1
p2=h2
node=Node(-1)
p3=node
while p1!=None and p2!=None:
if p1.data<p2.data:
p3.next=p1
p1=p1.next
elif p2.data<p1.data:
p3.next=p2
p2=p2.next
p3=p3.next
if p1!=None:
p3.next=p1
if p2!=None:
p3.next=p2
head=node.next
curr=head
prev=None
next=None
while curr:
next=curr.next
curr.next=prev
prev=curr
curr=next
head=prev
return head
我做错了什么?这个问题还有其他解决方法吗?
2条答案
按热度按时间798qvoo81#
问题出在这一行:
这里不应该有条件,因为您希望处理所有剩余的案例。现在你不处理这个案子
p2.data
等于p1.data
. 因此,将上述行更改为:这将解决问题。
另类
有一种较短的方法可以实现该结果:不必在第二阶段中反转列表,而是直接按相反顺序插入节点。这样,您就可以在一个循环中而不是两个循环中处理工作。然后,只要其中一个引用不存在,就应该继续循环
None
,所以while
情况变成了一个问题or
. 然后在if
你需要考虑这两者中的一个None
. 最后,你真的不需要介绍p1
及p2
变量:只需使用已经给出的h1
及h2
.此解决方案也不需要临时的“sentinel”节点(值为-1的节点)。
所以这里
h1
(或h2
)位于当前结果列表的前面。在它被预先指定之后,结果引用被放置到该预先指定的节点。多重赋值是这样的:h1
(或h2
)仍将走到(原始)下一个节点,在该节点的next
参考值已调整。当然,您也可以通过单独的赋值来完成此操作,但是您需要一个临时变量:a5g8bdjr2#
在mergeresult的while循环中,需要检查p1.data==p2.data。当前,您没有检查此项,因此当p1.data==p2.data时,没有设置p3.next(因此保持其默认值none)。这意味着p3被设置为无,如错误所示,p3.next(即none.next)不工作。