合并两个排序的链表

Question

我已经实现了一个合并排序链表的函数，但是最后一个节点没有合并。如果我将current.next设置为l2，我将得到无限循环。如果我删除它，它可以工作，但没有附加到新列表的最后一个节点。我做错了什么？

def merge(self,l1,l2):
    if l1.val < l2.val:
        current = l1
        l2 = l2
    else:
        current = l2
        l2 = l1
    while(current != None):
        if current.next == None and l2 != None:
            #current.next = l2 infinite loop if I include this
        elif current.next.val > l2.val:
            temp = current.next
            current.next = l2
            l2 = temp
        current = current.next

    self.printList(current) 

List1：5 7 16

list2：2 4 6 8 10

预期的2 4 5 6 7 8 10 16，当前结果的2 4 5 6 7 8 10

Answer 1

取自已接受的解决方案here，此算法修复您的解决方案：

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

Answer 2

我错过了角落案例的检查，这是一个修复：

def merge(self,l1,l2):
    if l1.val < l2.val:
        current = l1
        l2 = l2
    else:
        current = l2
        l2 = l1
    while(current != None):
        if current.next == None and l2 != None:
            current.next = l2
            l2 = None

        elif current.next != None and l2 != None and current.next.val > l2.val:
            temp = current.next
            current.next = l2
            l2 = temp
        current = current.next