LeetCode — Merge Two Sorted Lists

Problem Link: https://leetcode.com/problems/merge-two-sorted-lists/

Problem Description: 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.

A sample test case

Approach Used: Linked-List

Explanation: This is a straight-forward linked list question. We create a new output list which at starting points to null. At each point, we compare the head nodes of both list and add the node from one of the lists whichever has the smaller value. If both the nodes have equal value then we can push anyone of the two. We shift the head pointer to the next node for the list from which the head node is selected. We continue doing this until one of the lists becomes empty. At this point, we will have one non-empty list. Since this is the only list left we can merge the whole to the output list.

Code(Java):

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //if both lists are empty, then nothing needs to be done
        if(l1==null && l2==null)
            return null;
        
        //if any one of the lists is empty, then the output will be the other list
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        
        //new output list intially null
        ListNode l3 = null;
        
        //finding head node of the output list
        if(l1.val<l2.val){
            l3 = l1;
            l1=l1.next;
        }
        else{
            l3 = l2;
            l2 = l2.next;
        }
        
        //storing the head (this will be returned at the end, since l3 will be constantly modified)
        ListNode head = l3;
        
        //merging the nodes until we exhaust one of the lists.
        while(l1!=null && l2!=null){
            //appending node which has smaller value
            if(l1.val<l2.val){
                l3.next = l1;
                l1 = l1.next;
            }
            else{
                l3.next=l2;
                l2=l2.next;
            }
            //incrementing to next node to repeat the process
            l3=l3.next;
        }
        
        //if l1 still has any nodes left, attach all of them at end of output (so nothing left to compare)
        if(l1!=null)
            l3.next=l1;
        
        //if l2 still has any nodes left, attach all of them at end of output (so nothing left to compare)
        if(l2!=null)
            l3.next=l2;
        
        //returning starting node of final output (l3 would be pointing to some other node by now)
        return head;
    }

Complexity:
Space complexity: O(m+n) space needed to store all the nodes in the output list.
Time complexity: O(m+n) time needed to visit all the nodes of both input array.
Here m and n length of list1 and list2 respectively,