Merge Two Sorted Lists - how 2 nodes can be linked

Question

I want to ask a question about this merge 2 sorted linked lists exercise:

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

public class ListNode {
    int val; // value of the node = val 
    ListNode next; // this is the pointer to the next node, which is connected to this current node
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Here is my code

//21. Merge Two Sorted Lists
public class merge2linkedlists {

        public ListNode mergeTwoLists(ListNode l1, ListNode l2){
            ListNode output = new ListNode(0); //head 0 - will remove later         
            ListNode currentEnd = new ListNode(0); //the current end node
            output.next = currentEnd; // link head to the current end node
            
            
            while(l1 != null && l2 != null) {
                if(l1.val <= l2.val) {
                    currentEnd.next = l1; // link to the next node
                    l1 = l1.next; // move to the next node
                }
                else {
                    currentEnd.next = l2;
                    l2 = l2.next;
                }
                currentEnd = currentEnd.next; // change current end node
            }//end while
            
            if(l1 == null) {
                currentEnd.next = l2;
            }
            else {
                currentEnd.next = l1;
            }
            return output.next.next;
        }  


    //main function here
    public static void main(String[] args) {
        new merge2linkedlists();
    }

    public merge2linkedlists() {
        ListNode l1 = new ListNode(10); // head
        l1.next = new ListNode(80); 
        l1.next.next = new ListNode(150);
        l1.next.next.next = new ListNode(250);

        ListNode l2 = new ListNode(60); // head
        l2.next = new ListNode(100);
        l2.next.next = new ListNode(300);
        l2.next.next.next = new ListNode(800);

        System.out.print("\nList l1 ");
        l1.printLinkedList();

        System.out.print("\nList l2 ");
        l2.printLinkedList();

        ListNode output = mergeTwoLists(l1,l2);
        
        System.out.print("\nOutput ");
        output.printLinkedList();

    }
}

It runs correctly. But my question is that if I replace these 2 lines

ListNode currentEnd = new ListNode(0); //the current end node
output.next = currentEnd; // link head to the current end node

by ListNode currentEnd = output; and change the line return output.next.next; to be return output.next;it stills gives the correct answer, which I don't understand, because I don't see where the head of the output is linked to the currentEnd? Could you please let me know why? Thank you.

Answer 1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }*/
 

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp_node = new ListNode(0);
        ListNode current_node = temp_node ;

        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                current_node.next=l1;
                l1=l1.next;
            }
            else{
                current_node.next=l2;
                l2=l2.next;
            }
            current_node = current_node.next;
        }
        if(l1 == null){
            current_node.next = l2; 
        }
        else if(l2 == null){
            current_node.next = l1;
        }
    //    current_node.next = l1!=null ? l1:l2;
       return temp_node.next;
    }
    
}

Answer 2

When you use ListNode currentEnd = output; then your code does this:

output = new ListNode(0);
currentEnd = output;
// now both variables point to the same object

The first iteration of the while loop:

currentEnd.next = ...

This is effectively the same as output.next = ..., because you said output = currentEnd.

But at the end of the loop you change currentEnd:

currentEnd = currentEnd.next

This is effectively the same as currentEnd = output.next. But now you assigned a new value to currentEnd. This means that from now on output and currentEnd aren't the same anymore. output is still the same as before, because you didn't assign a new value to output. You only changed what currentEnd is pointing to.

---

Same same, but from another perspective:

Keep in mind that your variables* output and currentEnd are basically just pointers. Those variables do not store any data, they just store the memory location of your data. Your code works like this:

new ListNode(0) will create a new object in memory. Then you assign the memory location of that object to output (using output =). Next you assign the very same memory location to currentEnd (using currentEnd = output).

Now you still have a single object in memory, but 2 variables pointing to it.

Calling currentEnd.next = will go to the memory location of currentEnd (which is the same as for output in the first iteration of the loop), and then set within this memory location the next field.

At the end of the loop you do currentEnd = currentEnd.next. This will get the memory location of currentEnd.next and then says that currentEnd should point to this memory location. This does not change where output is pointing to. (If you want to change where output is pointing to, there's only one way: You must use output = ....)

I highly recommend that you take a sheet of paper and draw what happens in which order. Then things should become much clearer.

(*) this is only true for Objects in Java, but not for primitive types. But your code only uses Objects, though it's not important here.