对于以相反顺序合并2个排序的链表,我得到的是attributeerror'nonetype'对象对于某些测试用例没有属性'next'为什么?

euoag5mw  于 2021-08-20  发布在  Java
关注(0)|答案(2)|浏览(327)

我正在看《极客对极客的反向顺序合并2排序链表练习挑战》:
给定两个大小相同的链表 NM ,按非降序排序。任务是以这样一种方式合并它们,即结果列表按降序排列。

输入:

输入的第一行包含测试用例的数量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

我做错了什么?这个问题还有其他解决方法吗?

798qvoo8

798qvoo81#

问题出在这一行:

elif p2.data<p1.data:

这里不应该有条件,因为您希望处理所有剩余的案例。现在你不处理这个案子 p2.data 等于 p1.data . 因此,将上述行更改为:

else:

这将解决问题。

另类

有一种较短的方法可以实现该结果:不必在第二阶段中反转列表,而是直接按相反顺序插入节点。这样,您就可以在一个循环中而不是两个循环中处理工作。然后,只要其中一个引用不存在,就应该继续循环 None ,所以 while 情况变成了一个问题 or . 然后在 if 你需要考虑这两者中的一个 None . 最后,你真的不需要介绍 p1p2 变量:只需使用已经给出的 h1h2 .
此解决方案也不需要临时的“sentinel”节点(值为-1的节点)。

def mergeResult(h1,h2):
    result = None
    while h1 or h2:
        if not h2 or (h1 is not None and h1.data < h2.data):
            h1.next, result, h1 = result, h1, h1.next
        else:
            h2.next, result, h2 = result, h2, h2.next
    return result

所以这里 h1 (或 h2 )位于当前结果列表的前面。在它被预先指定之后,结果引用被放置到该预先指定的节点。多重赋值是这样的: h1 (或 h2 )仍将走到(原始)下一个节点,在该节点的 next 参考值已调整。当然,您也可以通过单独的赋值来完成此操作,但是您需要一个临时变量:

def mergeResult(h1,h2):
    result = None
    while h1 or h2:
        if not h2 or (h1 is not None and h1.data < h2.data):
            nxt = h1.next
            h1.next = result
            result = h1
            h1 = nxt
        else:
            nxt = h2.next
            h2.next = result
            result = h2
            h2 = nxt
    return result
a5g8bdjr

a5g8bdjr2#

在mergeresult的while循环中,需要检查p1.data==p2.data。当前,您没有检查此项,因此当p1.data==p2.data时,没有设置p3.next(因此保持其默认值none)。这意味着p3被设置为无,如错误所示,p3.next(即none.next)不工作。

相关问题