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

Question

我正在做 leetcode 问题 21（合并两个排序列表）

合并两个已排序的链表，return将其作为一个已排序的列表。列表应该由前两个列表的节点拼接而成。

输入：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)和return res.next 作为输出？这里的虚拟节点有什么作用？

虽然上面的代码有效，但我也不明白为什么。我们初始化了res作为虚拟节点，但是在后续代码中我们根本没有改变变量dummy。所以 dummy 应该始终保持为 ListNode(None)，我们应该 return res.next 而不是 dummy.next。那为什么我们最后要returndummy.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?

Answer 1

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

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

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

Can't understand when to use dummy node in leetcode questions

python

linked-list