[FIXED] Two linked lists change simultaneously

Issue

I know this question has been asked a lot in different settings (here for example) but not always in very simple terms, and I just didn't get the previous answers.

In a very simple setting, here is my issue: I just don't understand why the dummy_head is actualized whereas I seemingly don't do any operation on it. Is it a python property, or specific to linked list? Can someone please explain what happens line by line?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    
        dummy_head = ListNode(0)
        other_list = dummy_head
    
        for i in range(1, 3):
            other_list.next = ListNode(i) 
            other_list = other_list.next
        
        print('dummy_head:', dummy_head)
        print('other_list', other_list)

Here is the output I get:

dummy_head: ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 2, next: None}}}
other_list ListNode{val: 2, next: None}

Thanks for your help!

Solution

I just don't understand why the dummy_head is actualized whereas I seemingly don't do any operation on it.

Actually there is an operation on it. In the first iteration of the loop, its next attribute is assigned a value. This is a bit hidden, but that first iteration starts with other_list being a synonym for dummy_head, so the assignment to next is mutating dummy_head.

Is it a python property, or specific to linked list?

Neither. It is just an extra node that is created, and its purpose is to simplify the rest of the code. Here is what the code would look like without the use of such a dummy:

head = None # No dummy node now
other_list = None

for i in range(1, 3):
    if other_list is None:  # We distinguish 
        head = ListNode(i)
        other_list = head
    else:
        other_list.next = ListNode(i) 
        other_list = other_list.next

return head

Note also, that it is never the purpose to print dummy_head as you did. Almost always, it is dummy_head.next that is returned by such a function. There is no interest in the end to the dummy_head itself. And that dummy_head.next corresponds to what I have called head in the alternative script above.

Can someone please explain what happens line by line?

It may help to visualise it:

Before the loop starts, this state is created -- note that both names reference the same node.

 dummy_head
  ↓
┌───────────┐    
│ value: 0  │
│ next: None│
└───────────┘
  ↑ 
 other_list 

In the first iteration of the loop i is 1, and other_list.next = ListNode(i) is executed. The first thing that happens is the call ListNode(i). This results in:

 dummy_head      (ListNode(i))
  ↓                ↓
┌───────────┐    ┌───────────┐    
│ value: 0  │    │ value: 1  │
│ next: None│    │ next: None│
└───────────┘    └───────────┘
  ↑ 
 other_list 

The reference to that node is then assigned to other_list.next. So we get:

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    
│ value: 0  │    │ value: 1  │
│ next: ───────> │ next: None│
└───────────┘    └───────────┘
  ↑ 
 other_list 

The last thing that happens in that first iteration is the assignment other_list = other_list.next:

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    
│ value: 0  │    │ value: 1  │
│ next: ───────> │ next: None│
└───────────┘    └───────────┘
                   ↑ 
                  other_list 

The next iteration of the loop, with i is 2, will go through the same steps and produce this:

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 0  │    │ value: 1  │    │ value: 2  │
│ next: ───────> │ next: ───────> │ next: None│
└───────────┘    └───────────┘    └───────────┘
                                    ↑ 
                                   other_list 

And the final iteration produces:

 dummy_head      
  ↓                
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 0  │    │ value: 1  │    │ value: 2  │    │ value: 3  │
│ next: ───────> │ next: ───────> │ next: ───────> │ next: None│
└───────────┘    └───────────┘    └───────────┘    └───────────┘
                                                     ↑ 
                                                    other_list 

Usually such a function would end with return dummy_head.next, which signifies that the real list does not include the dummy node. The caller will then get a reference to this list:

┌───────────┐    ┌───────────┐    ┌───────────┐
│ value: 1  │    │ value: 2  │    │ value: 3  │
│ next: ───────> │ next: ───────> │ next: None│
└───────────┘    └───────────┘    └───────────┘

Hope this clarifies it.

Answered By - trincot