Merging two sorted lists in Java, reference question

Question

I am merging two sorted singly linked lists of integers. Each node has a value, and the reference of the next node. The code written is functional and has passed all relevant test cases.

How does the head3 node point to the next correct node in the sorted merged singly linked list, when it is never updated?

static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    
    if (head1 == null) return head2;
    if (head2 == null) return head1;
    
    SinglyLinkedListNode head3 = null;
    if(head1.data < head2.data){
        head3 = head1;
        head1 = head1.next;
    } else{
        head3 = head2;
        head2 = head2.next;
    }
    SinglyLinkedListNode current_node = head3;
    while(head1 != null && head2 != null){
        if(head1.data < head2.data){
            current_node.next = head1;
            head1 = head1.next;
        } else{
            current_node.next = head2;
            head2 = head2.next;
        }
        current_node = current_node.next;
    } 
    if(head1 == null){
        current_node.next = head2;
    } else {
        current_node.next = head1;
    }
    return head3;
}

Current_node is declared and assigned the same value and reference of next node as head3. However, in the following while loop, the reference of the next node is updated (current_node.next), depending on the comparison statements. head3 is never updated, and still has the next node reference it had in the initial if else statement (head3.next).

When head3 is returned, it should point to the next node in the merged sorted singly linked list, but this reference is never changed. Why?

There are no memory addresses in Java. Only references. Please restate your question using the correct terminology. — user207421
– user207421, Commented Mar 28, 2022 at 23:42

rcgldr · Accepted Answer · 2022-03-28 23:44:09Z

1

head3 is initialized one time at the start, a copy of either head1 or head2. current_node is then used to append nodes to the list that starts with head3. Try different data values in the linked lists so that sometimes head1.data < head2.data and sometimes head1.data > head2.data in order to see that head3 is not always the same after a merge.

For a proper merge to be used for a stable merge sort, the compare should be head1.data <= head2.data .

answered Mar 28, 2022 at 23:44

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

regamblr Over a year ago

after head3 initialization (eg. a copy of head1), current_node is then initialized to be a copy of head3. current_node.next is then updated, but head3.next is not. My question is specifically about how current_node is used to append nodes to the list that starts with head3, since head3.next is never changed after initialization.

rcgldr Over a year ago

@lgdl.y - After current_node = head3; , both current_node and head3 will be references to the same node, so when current_node.next is updated, then head3.next will be updated as well.

Collectives™ on Stack Overflow

Merging two sorted lists in Java, reference question

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related