python - 无法理解何时在 leetcode 问题中使用虚拟节点

Question

我正在处理 leetcode 问题 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(None) 并返回 res.next 作为输出？虚拟节点在这里的作用是什么？

虽然上面的代码有效，但我也不明白为什么。我们将res初始化为 dummy 节点，但是在后续代码中我们根本没有更改变量dummy。所以 dummy 应该一直保持为 ListNode(None)，我们应该返回 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?

标签： pythonlinked-list

Answer 1

在整个 while 循环中，res变量实际上是前进的，请参阅res = res.next.

但 dummy 始终指向初始节点。因此，您仍然需要能够访问整个 ListNode，而不仅仅是在res执行结束时指向的最后一个节点。