Why is dummy node changing in this linked-list problem? (python3)

Question

I've read several explanations & watched 6 YouTube videos and still don't understand what's going on in the solution to this leetcode problem. Can someone explain the relationship between dummy and cur & also dummy and cur.next-- in the simplest terms possible? Specifically, I'm confused on the following:

This is the code I'm referring to (I included a bunch of print statements to try to understand what lines of code are causing dummy to change).

   cur = dummy = ListNode()
    iteration=1
    while list1 and list2:
        print("\n iteration=", iteration)
        print("list1.val & list2.val=",list1.val," & ",list2.val)
        print("****dummy=",dummy)

        if list1.val < list2.val:
            print("\n first block")
            cur.next = list1
            print("cur.next=",cur.next)
            print("****dummy=",dummy)
            list1, cur = list1.next, list1
            print("list1 & cur=",list1, " & \n", cur)
            print("****dummy=",dummy)
        else:
            print("\n second block")
            cur.next = list2 #cur.next=something --> dummy.next=something
            print("cur.next=", cur.next)
            print("****dummy=",dummy)
            list2, cur = list2.next, list2 #cur=something does not change dummy
            print("list2 & cur=",list2, " & \n ", cur)
            print("****dummy=",dummy)

        if list1 or list2:
            print("\n third block")
            cur.next = list1 if list1 else list2
            print("cur.next=",cur.next)
            print("****dummy=",dummy)



        iteration+=1
    print("\n cur=",cur)
    print("****dummy=",dummy)

    return dummy.next

This is the output for the first iteration:

iteration= 1
list1.val & list2.val= 1  &  1
****dummy= ListNode{val: 0, next: None}

 second block
cur.next= ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
****dummy= ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}}
list2 & cur= ListNode{val: 3, next: ListNode{val: 4, next: None}}  &
  ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
****dummy= ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}}

 third block
cur.next= ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}
****dummy= ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}}}

Okay, so what I noticed from above, in the second block: cur.next=something, sets dummy.next=something. But then, cur=something, does not set dummy=something. Why is this? Then, in the third block, cur.next=something sets dummy.next.next =something (the something is linked to 0,1 instead of 0 as it was in the second block. Why is this? Overall, I'm just pretty confused on the whole "pointer" thing and can't understand how cur & cur.next are related to dummy & dummy.next & dummy.next.next and so on.

Answer 1

The idea for this problem is to create a "sentinel" node which corresponds to dummy. This will be a "dummy" node representing the head of a new linked list that will be the "resultant" linked list constructed after performing the merge.

# sentinel node
dummy = ListNode(-1)

# visual of `dummy` linked list
-1 -> None

The variable cur is simply a pointer to the "head" of the dummy linked list which we will use to insert new nodes while merging list1 and list2. Using cur.next = some_node represents inserting a new node after cur in the dummy linked list.

# sentinel node
dummy = ListNode(-1)

# pointer to head of "dummy" linked list
cur = dummy

# both dummy and cur are positioned at the "head" node with value -1
-1 -> None

# inserting a new node to the "dummy" list would look like
cur.next = ListNode(2)

# cur = dummy at this point so cur is still at the first node -1
# the linked list would have 2 nodes and cur.next equals node 2
dummy
cur
-1 -> 2 -> None

# since cur is still at the "dummy" node equaling -1, we want to move `cur`
# to the newly inserted node, this allows `cur` to be ready 
# for another insertion at the correct position in the linked list
cur = cur.next

dummy  cur
-1   -> 2 -> None

# dummy.next would represent a linked list with a single node 2
2 -> None

Below is an iterative approach similar to your logic with comments to better illustrate how we insert nodes into the "dummy" linked list using cur and continue moving the list1 and list2 node pointers as we iterate the two linked lists:

# list1=[1,2,4]
# list2=[1,3,4]

# O(n+m) time and O(1) space
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # create a "dummy" node to represent 
    # resultant merged linked list
    dummy = ListNode(-1)

    # place cur pointer at head of dummy linked list
    cur = dummy

    # iterate both linked lists
    while list1 and list2:

        if list1.val <= list2.val:
            # insert node into the dummy list by updating
            # the "next" reference of `cur` to equal list1 node
            cur.next = list1

            # continue moving the list1 node to the "next" node in list1
            list1 = list1.next
        else:
            # insert node into the dummy list by updating
            # the "next" reference of `cur` to equal list2 node
            cur.next = list2

            # continue moving the list2 node to the "next" node in list2
            list2 = list2.next
        
        # keep moving the cur pointer as we insert to the dummy list
        cur = cur.next

    # there can be one value left to merge from one of the
    # two lists so insert the final node to complete the merge
    cur.next = list1 or list2

    # return dummy.next which skips the `dummy` node -1 and 
    # points to the new "head" of resultant merged list
    # -1 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 
    return dummy.next

Answer 2

curr and dummy are used to reference to same node (listNode), now curr is modified (ie a node from any of two linked list is referenced) and the node that it reference to is referencing another node and so on . now the state of curr is different that what it used to be earlier at creation (ie it reference to None as all merging is done) while dummy still referencing to first node only.

thus we can with the help of this dummy can get all the nodes these are referencing to , ie a merged linked list

dummy.next is used to get the first node of resultant linked list from the current linked list(having dummy as head node)

Answer 3

The = operator between objects in Python results in both variable names referencing the same object in memory. Initially, cur and dummy refer to the same ListNode object, as opposed to cur being a different ListNode object with the same values. Therefore changes made to either will affect the other. Here explains assignment vs shallow copy vs deep copy in Python.

When you reassign cur to list1 the link between cur and dummy is gone.

EDITED: corrected mention of shallow copy for talking in terms of references, subject to comments.