将两个已排序的链接列表合并到python中的一个链接列表中

发布时间：2020-12-20 12:30:59 所属栏目：Python 来源：网络整理

导读：这是我的代码： def merge_lists(head1,head2): if head1 is None and head2 is None: return None if head1 is None: return head2 if head2 is None: return head1 if head1.value head2.value: temp = head1 else: temp = head2 while head1 != None and

这是我的代码：

def merge_lists(head1,head2):
    if head1 is None and head2 is None:
        return None
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    if head1.value < head2.value:
        temp = head1
    else:
        temp = head2
    while head1 != None and head2 != None:
        if head1.value < head2.value:
            temp.next = head1
            head1 = head1.next
        else:
            temp.next = head2
            head2 = head2.next
    if head1 is None:
        temp.next = head2
    else:
        temp.next = head1
    return temp
    pass

这里的问题被困在无限循环中.任何人都告诉我问题是什么

例子是：

assert [] == merge_lists([],[])
 assert [1,2,3] == merge_lists([1,3],3] == merge_lists([],[1,3])
 assert [1,1,3,4,5] == merge_lists([1,5])

解决方法

当前代码的问题在于,在导航到当前节点的下一个节点之前,它会导致临时节点的副作用.当前临时节点是当前节点时,这是有问题的.

也就是说,想象一下这种情况：

temp = N
temp.next = N  # which means N.next = N
N = N.next     # but from above N = (N.next = N) -> N = N

有一个更正版本,还有一些其他更新：

def merge_lists(head1,head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1

    # create dummy node to avoid additional checks in loop
    s = t = node() 
    while not (head1 is None or head2 is None):
        if head1.value < head2.value:
            # remember current low-node
            c = head1
            # follow ->next
            head1 = head1.next
        else:
            # remember current low-node
            c = head2
            # follow ->next
            head2 = head2.next

        # only mutate the node AFTER we have followed ->next
        t.next = c          
        # and make sure we also advance the temp
        t = t.next

    t.next = head1 or head2

    # return tail of dummy node
    return s.next

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!