Why return node.next will return the whole linked list?

user_19504764 0
Viewed 32

I am new to coding and am working on LeetCode#21 Merge two sorted list.

An example: Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

A common solution to this question is:

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

    class Solution:
        def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
            dummy = ListNode()
            tail = dummy

            while list1 and list2:
                 if list1.val < list2.val:
                    tail.next = list1
                    list1 = list1.next
                 else:
                    tail.next = list2
                    list2 = list2.next
                 tail = tail.next

            if list1:
                 tail.next = list1
            elif list2:
                 tail.next = list2

            return dummy.next

I am confused with the last line: return dummy.next

Shouldn't it simply return the next node of dummy node? How will that return the whole list?

array-merge linked-list merge python-3.x
1 Answers

Dummy is created as a temporary head, because at the start we don't know whether our head starts with list1 or list2.

After we are done merging, dummy will look like this. The dummy value is 0 because this is the default value when you call ListNode().

0 > 1 > 1 > 2 > 3 > 4 > 4

But our original list does not have 0, therefore 0 is removed by dummy.next

dummy.next will look like this.

1 > 1 > 2 > 3 > 4 > 4

This will return the whole list because each ListNode stores its next value in the self.next property.

You can check with this. We know we have reached the end node of the linked list when its self.next is None.

current = dummy.next;
while current is not None:
    print(current.val);
    current = current.next;
user_85581740
Related