Assignment of singly-linked list in java

Question

We have the following approach to merge two singly-linked list in java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //the next node of dummy will be pointing at the final result so it is easier to return
        ListNode dummy = new ListNode(0);
        ListNode result = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                result.next = l1;
                l1 = l1.next;
            } else {
                result.next = l2;
                l2 = l2.next;
            }
            result = result.next;
        }

        if (l1 != null) {
            result.next = l1;
        } else {
            result.next = l2;
        }

        return dummy.next;
    }
}

My question is after assigning dummy to result, dummy changes as result changes. This is intuitively correct because when I access the next of result, I am accessing the next of dummy.

However, for when I have an assignment like int a = 5; and change reassign a = 6, we would not get 5 == 6 apparently.

Or if I do result = ListNode(1), my guess is dummy would not be changed to ListNode(1).

What is the logic behind their distinctions?

Java is pass-by-value, always. That means that you can not have linkages like `first -> second -> instance`. When you do `second = first;` you have `first -> instance` and `second -> instance`. — Zabuzard, Nov 10 '19 at 15:26

kaya3 · Accepted Answer · 2019-11-10T15:31:58.277

The "box" metaphor for variables works fine with primitive values - imagine a box called a, which you put the number 5 in, then create a box called b and copy the 5 from a into that box. Now you can put a different number in a but box b still has the number 5.

This metaphor breaks down when a variable holds a reference to an object (e.g. a ListNode), because an object is not really the same kind of thing as a primitive value; the object itself is never stored "in" a variable. When you write code like ListNode dummy = new ListNode(0); you are not creating an object and storing it in a box named dummy - you are creating an object and storing a reference to it in the box named dummy.

For a better analogy, think of house addresses. Make a box named dummy and in it, put the address of your friend's house. Then make another box named result and put a copy of that address in the new box. Now, if your next instruction is "go to the house at the address in the dummy box and paint it blue", you should not be surprised that afterwards, the house at the address in the result box has also been painted blue; they are the same house, after all.

Assignment of singly-linked list in java

1 Answers1