CODEWITHSUNDEEP
pythonlinked-list
Cairo
Cairo

Reputation: 21

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

I am working on the leetcode question 21 (Merge Two Sorted Lists)

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Input: l1 = [1,2,4], l2 = [1,3,4]

Output: [1,1,2,3,4,4]

A typical python solution looks like this:

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

My question is: why can't I just define res as res = ListNode(None) at the beginning and return res.next as the output? What's the function of the dummy node here?

Although the above code works, I also can't understand why. We initiated res as the dummy node, but we did not change the variable dummy at all in the subsequent code. So dummy should remain as ListNode(None)the entire time, and we should return res.next instead of dummy.next. Then why do we return dummy.next at the end?

To illustrate better, I think the code above is doing something similar to the below example, which does not make much sense to me

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?

Upvotes: 1

Views: 784

Answers (1)

Fred.W
Fred.W

Reputation: 71

throughout the while loop, the res variable actually advances, see res = res.next.

But dummy is always pointing to the initial node. So you sill need that to be able to access to the whole ListNode, not just the last node as res is pointing to at the end of execution.

Upvotes: 2

Related Questions