CODEWITHSUNDEEP
python-3.xlinked-list
romesh prasad
romesh prasad

Reputation: 15

Linkedlist : How does the dummy node gets the result

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        x = ListNode()
        tail = x
        while list1 and list2:
            if  list1.val <= list2.val:
                tail.next = list1
                # print(tail.next)
                list1 = list1.next
            else:
                tail.next = list2
                # print(tail.next)
                list2 = list2.next
            tail = tail.next
        if list1:
            tail.next = list1
            # print(tail.next)
        else:
            tail.next = list2
            # print(tail.next)
        
        # print(x.next)
        return x.next

Inputs
list1 =
[1,2,4]
list2 =
[1,3,4]
Output for the above code:
Expected solution and my output is similar
[1,1,2,3,4,4]

Print : However I do not understand the below part where it prints the values inside the listnode
ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}
ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
ListNode{val: 2, next: ListNode{val: 4, next: None}}
ListNode{val: 3, next: ListNode{val: 4, next: None}}
ListNode{val: 4, next: None}
ListNode{val: 4, next: None}
ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 4, next: None}}}}}}

When I print the code at first if loop I get the tail.next value as the values inside the list1. Similarly if you see the print output it shows all the tail.next values, however according to my logic the tail.next value should only contain the value of the list which I am comparing. For example: in first case I compare 1 vs 1 and the output should be 1. However if I print tail.next I see that the values are 1,2,4. I don't understand why???

Upvotes: 0

Views: 34

Answers (1)

trincot
trincot

Reputation: 350715

tail.next is not an isolated node. It has a next attribute of its own.

Here is a small visualisation of the example you have given:

At the start of the function, the dummy node x is created (with default value 0), and also tail gets a reference to it:

                  list1
                   │
                 ┌─┴──────────┐    ┌────────────┐    ┌────────────┐
                 │ val:  1    │    │ val:  2    │    │ val:  4    │
                 │ next: ──────────┤ next: ──────────┤ next: None │
  x              └────────────┘    └────────────┘    └────────────┘
  │
┌─┴──────────┐
│ val:  0    │
│ next: None │
└─┬──────────┘
  │
 tail            ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ val:  1    │    │ val:  3    │    │ val:  4    │
                 │ next: ──────────┤ next: ──────────┤ next: None │
                 └─┬──────────┘    └────────────┘    └────────────┘
                   │
                  list2

In the first iteration of the loop, the if condition is true, so tail.next = list1 gets executed, which mutates the dummy node's next attribute:

                  list1
                   │
                 ┌─┴──────────┐    ┌────────────┐    ┌────────────┐
                 │ val:  1    │    │ val:  2    │    │ val:  4    │
              ┌──┤ next: ──────────┤ next: ──────────┤ next: None │
  x           │  └────────────┘    └────────────┘    └────────────┘
  │           │
┌─┴──────────┐│
│ val:  0    ││
│ next: ──────┘
└─┬──────────┘
  │
 tail            ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ val:  1    │    │ val:  3    │    │ val:  4    │
                 │ next: ──────────┤ next: ──────────┤ next: None │
                 └─┬──────────┘    └────────────┘    └────────────┘
                   │
                  list2

And as you can see tail has been prefixed to list1, which itself has a chain of nested node references. By consequence those nodes now also are reachable through tail.

By the same logic that printing list1 will output a nested structure containing 1, 2, and 4 values, printing tail will output a nested structure containing 0, 1, 2, and 4 values.

See also Merging two linked lists - how does the dummy node get updated? for a detailed explanation of how the rest of the merge algorithm does the job.

Upvotes: 1

Related Questions