CODEWITHSUNDEEP
pythonlinked-list
jessefournier
jessefournier

Reputation: 193

Setting a next value for a linkedlist function

I'm looking at This LeetCode Question about LinkedList and there's something I don't understand about the answer.

In the code below, I have copied the answer from above and added a comment in the place I want to refer to:

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

def addTwoNumbers(l1,l2):
    dummyHead = ListNode(0)
    curr = dummyHead
    carry = 0
    while l1 != None or l2 != None or carry != 0:
        l1Val = l1.val if l1 else 0
        l2Val = l2.val if l2 else 0
        columnSum = l1Val + l2Val + carry
        carry = columnSum // 10
        newNode = ListNode(columnSum % 10)
        #####################
        curr.next = newNode #
        curr = newNode      #    <- Part 1
        ##############################
        l1 = l1.next if l1 else None # <- Part 2
        l2 = l2.next if l2 else None #
        ##############################
    return dummyHead.next

l1 = ListNode(1)
l2 = ListNode(2)
print(addTwoNumbers(l1=l1,l2=l2).val)
  1. In the section I marked as Part 1, why set curr.next to newNode and then completely overwrite it with curr = newNode? I checked, and it seems like it overwrites the value completely, and thus removing the next in curr.
  2. In the section I marked as Part 2, doesn't the following line: l1 = l1.next overwrite everything yet again?
  3. How does returning dummyHead.next works? This value wasn't modified, it's just an empty list in the beginning

I tried to debug but I still haven't gotten much out of it. I'm trying to learn LinkedList from this example and would appreciate any help. Huge thanks ahead!

Upvotes: 0

Views: 357

Answers (1)

trincot
trincot

Reputation: 350300

why set curr.next to newNode and then completely overwrite it with curr = newNode?

These are two different type of assignment. The first -- assigning to curr.next -- mutates whatever object that curr is referencing. The second -- curr = newNode -- merely changes what curr references to. It doesn't mutate the data structure. It may help to visualise what happens. Let's say curr references a ListNode instance with value 1:

curr
  │
┌─┴──────────┐
│ val: 1     │
│ next: None │
└────────────┘

And newNode was just created with a value 2:

curr              newNode
  │                 │
┌─┴──────────┐    ┌─┴──────────┐
│ val: 1     │    │ val: 2     │
│ next: None │    │ next: None │
└────────────┘    └────────────┘

Then the first assignment -- curr.next = newNode will accomplish this:

curr              newNode
  │                 │
┌─┴──────────┐    ┌─┴──────────┐
│ val: 1     │    │ val: 2     │
│ next: ──────────┤ next: None │
└────────────┘    └────────────┘

And the second assignment, leads to this state:

                  curr newNode
                    │    │
┌────────────┐    ┌─┴────┴─────┐
│ val: 1     │    │ val: 2     │
│ next: ──────────┤ next: None │
└────────────┘    └────────────┘

The same would have happened, if the second assignment would have been curr = curr.next, since at that point curr.next and newNode reference the same object. This should also explain the rationale for your second point concerning l1 = l1.next. This merely traverses one step through a linked list with a variable. It doesn't affect that linked list itself.

How does returning dummyHead.next works? This value wasn't modified, it's just an empty list in the beginning.

The list was modified. But it happened via a different variable... curr. Note how initially curr references the same object as dummyHead, and then in the loop, the assignment to curr.next is setting the next attribute that dummyHead references, so that now dummyHead.next references a list with one element. And curr will move on to reference that element, and again set its next attribute, making that linked list having 2 nodes, ...etc

Upvotes: 1

Related Questions