объединение двух отсортированных связанных списков python

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

Я пропустил проверки на угловых случаях, вот исправление:

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

Answer 2

взято из принятого решения здесь этот алгоритм исправляет ваш:

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