• + 0 comments

    My Java solution with linear time complexity and constant space complexity:

    static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
            //handle edge cases where there is no other list to merge
            if(head1 == null) return head2;
            if(head2 == null) return head1;
            
            //determine the new head of the merged linked list
            SinglyLinkedListNode head;
            if(head1.data <= head2.data){
                head = head1;
                head1 = head1.next;
            }
            else{
                head = head2;
                head2 = head2.next;
            }
            
            //iterate through both linked lists, sorting asc
            SinglyLinkedListNode curr = head;
            while(head1 != null && head2 != null){
                if(head1.data <= head2.data){
                    curr.next = head1;
                    head1 = head1.next;
                }
                else{
                    curr.next = head2;
                    head2 = head2.next;
                }
                curr = curr.next;
            }
            
            //append any extra vals to the merged linked list
            if(head1 != null) curr.next = head1;
            else if(head2 != null) curr.next = head2;
            
            return head;
        }