在python中将两个排序的链表合并为一个链表 [英] merging two sorted linked lists into one linked list in 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 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

这里的问题卡在了死循环中.谁能告诉我是什么问题

the problem here is stucked in the infinite loop.can any one tell me what the problem is

示例如下:

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

推荐答案

当前代码的问题是它导致临时节点的下一个 before 导航到下一个节点的副作用从当前节点.当当前临时节点是当前节点时，这是有问题的.

The problem with the current code is that it causes a side-effect of the temp node's next before it navigates to the next node from the current node. This is problematic when the current temp node is the current node.

也就是说，想象一下这种情况:

That is, imagine this case:

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

有一个更正的版本，还有一些其他更新:

There is a corrected version, with some other updates:

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

这篇关于在python中将两个排序的链表合并为一个链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！