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?

CodePudding user response：

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 .