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

Question

Я решаю вопрос Leetcode (Задача № 21), который берет два отсортированных связанных списка и возвращает отсортированный, объединенный связанный список.Например, ввод: 1-> 2-> 4, 1-> 3-> 4 и вывод: 1-> 1-> 2-> 3-> 4-> 4.

Я не суперопыт работы со связанными списками, но я пытаюсь решить больше проблем, чтобы получить доступ.Вместо того, чтобы возвращать желаемый результат, [1,1,2,3,4,4], мой код просто возвращает [4].Тем не менее, я думаю, что основная логика есть, и я надеюсь, что упускаю что-то маленькое.

def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        newList = ListNode(0) # used for single, merged list
        while l1 and l2:
            if l1.val <= l2.val: # compare current node's values
                newList.next = l1
                l1 = l1.next
            else:
                newList.next = l2
                l2 = l2.next

        return newList.next # first node is 0, which we don't want

Answer 1

a1=[3,9,1]
a2=[8,3,4]

a = a1 + a2
a.sort()

Должен сделать свое дело.

Answer 2

Основная логика почти готова, но вы заменяете только следующий элемент в списке каждый раз (вы не продвигали список), таким образом, вы возвращаете только последний элемент.Решение состоит в том, чтобы создать еще один «указатель cur» для продвижения списка, сохраняя newList в качестве «переднего указателя» для возврата результата.

Также в конце вы должны «конкатить» с непустым списком

def mergeTwoLists(self, l1, l2):
    newList = ListNode(0)
    cur = newList 
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2 # add non-empty list
    return newList.next