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!

CodePudding user response：

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.

CodePudding user response：

When you do other_list = dummy_head, other_list is just a reference to dummy_head. It's not a copy. So when you modify other_list it also modify dummy_head, because they are pointing the same object. You have to copy dummy_head or create a new Object. Your problem deals with Mutable and Immutable Objects in Python. It's a bit complicated to explain so you can read this link to understand this notion.

https://medium.com/@meghamohan/mutable-and-immutable-side-of-python-c2145cf72747

CodePudding user response：

The operator = is for name-binding.

The statement dummy_head = ListNode(0) binds the name dummy_head to the value of the expression ListNode(0). The expression to the right of the = operator is evaluated before the name-binding. Here, the expression ListNode(0) is evaluated to an instance of the class ListNode.

The following statement other_list = dummy_head, which is another name-binding statement, binds the name other_list to the value of the expression dummy_head. Again, before the name-binding, the expression to the right of = must be evaluated. The expression dummy_head is actually a bound name, so it is evaluated to the value bound to the name, which is that ListNode instance created before. Hence after this statement, those two names other_list and dummy_head are both bound to the same value - that instance of ListNode.