Блог

Я работаю над вопросом 21 по литкоду (Объединение двух отсортированных списков)

Объедините два отсортированных связанных списка и верните их в виде отсортированного списка. Список должен быть составлен путем объединения узлов первых двух списков.

Входные данные: l1 = [1,2,4], l2 = [1,3,4]

Вывод: [1,1,2,3,4,4]

Типичное решение на python выглядит следующим образом:

 class Solution:
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(None)
        res = dummy
       # why can't I just define res as res = ListNode(None)
        
        while l1 and l2:
            if l1.val<= l2.val:
                res.next = l1
                l1 = l1.next
            else:
                res.next = l2
                l2 = l2.next
            res = res.next
            
        if l1: 
            res.next = l1
        if l2:
            res.next = l2
        return dummy.next
 

Мой вопрос: почему я не могу просто определить res как res = ListNode(нет) в начале и вернуть res.next в качестве вывода? Какова функция фиктивного узла здесь?

Хотя приведенный выше код работает, я также не могу понять, почему. Мы инициировали res как фиктивный узел, но мы вообще не изменили фиктивную переменную в последующем коде. Таким образом, dummy должен оставаться в качестве ListNode(Нет)все время, и мы должны возвращать res.next вместо dummy.next. Тогда почему мы возвращаем dummy.next в конце?

Чтобы лучше проиллюстрировать, я думаю, что приведенный выше код делает что-то похожее на приведенный ниже пример, что для меня не имеет особого смысла

 a = 3
b = a
b = b 2  #or any code that changes something in b, but does not change a
return a # and the output turns out to be a =5, which is clearly a wrong answer

##############################
The above linked list did similar things:

dummy = ListNode(None)
res = dummy

some other code #The while loop that did something to res, but did nothing to dummy

return dummy 
#how can we possibly get a dummy that is not None, since the while loop did nothing to it?
 

на протяжении всего цикла while res переменная фактически продвигается res = res.next вперед, см.

Но манекен всегда указывает на начальный узел. Таким образом, вам это нужно, чтобы иметь доступ ко всему ListNode, а не только к последнему узлу, res на который указывает в конце выполнения.