CODEWITHSUNDEEP
data-structuresmergelinked-listsingly-linked-list
Sarthak Thakur
Sarthak Thakur

Reputation: 25

Why does the head pointer lose track of the linkedlist when overwriting the current head node

Comparing:

public static ListNode mergeTwoLists(ListNode list1, ListNode list2)
    {
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;

        while (list1 != null && list2 != null)
        {
            if (list1.val < list2.val)
            {
                dummy.next = list1;
                list1 = list1.next;
            }
            else
            {
                dummy.next = list2;
                list2 = list2.next;
            }

            dummy = dummy.next;
        }
        if (list1 == null)
        {
            dummy.next = list2;
        }
        else if (list2 == null)
        {
            dummy.next = list1;
        }
        return head.next;
    }

To:

 public static ListNode mergeTwoLists(ListNode list1, ListNode list2)
        {
            ListNode dummy = new ListNode(-1);
            ListNode head = dummy;

        while (list1 != null && list2 != null)
        {
            if (list1.val < list2.val)
            {
                dummy = list1;
                list1 = list1.next;
            }
            else
            {
                dummy = list2;
                list2 = list2.next;
            }

            dummy = dummy.next;
        }
        if (list1 == null)
        {
            dummy.next = list2;
        }
        else if (list2 == null)
        {
            dummy.next = list1;
        }
        return head.next;
    }

What is the difference in respect to how head points to the dummy ListNode.

My understanding was instead of using dummy.next = list1 and just having dummy = list1, we would essentially be rewriting the current value of dummy. Then when we get to:

dummy = dummy.next;

Dummy will equal null. So when we get to the next iteration of the loop we will resassign null to the whatever node is in list1. So why is head not able to keep track of dummy when we do this? Is it because we are assigning the first node of dummy to a different list?

Upvotes: 0

Views: 225

Answers (1)

trincot
trincot

Reputation: 350270

You can only mutate a list by assigning values to properties of nodes, not by assigning values to local variables.

Just like list1 = list1.next does not alter list1, but merely moves a reference to the next node in that list, so dummy = list1 does not alter that list either. It merely sets a reference to a node; nothing alters in that list.

So in your second version, dummy starts as reference to a node with value -1, but then in the first iteration of the loop abandons that node, and refers to another node in list1. So the node with value -1 never gets anything assigned to its next member, which remains null until the very end of the function's execution.

Upvotes: 1

Related Questions