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

euoag5mw 于 2021-08-20 发布在 Java

关注(0)|答案(2)|浏览(231)

我正在看《极客对极客的反向顺序合并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

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

python sorting linked-list

来源：https://stackoverflow.com/questions/68311810/for-merging-2-sorted-linked-list-in-reverse-order-i-am-getting-attributeerror-n

2条答案

按热度按时间

798qvoo81#

问题出在这一行：

elif p2.data<p1.data:

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

else:

这将解决问题。

另类

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

赞(0）回复(0）举报 2021-08-20

a5g8bdjr2#

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

赞(0）回复(0）举报 2021-08-20