Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• 100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Solution

EXPLANATION

• Maintain a head and a tail pointer on the merged linked list.
• Then choose the head of the merged linked list by comparing the first node of both linked lists.
• For all subsequent nodes in both lists, you choose the smaller current node and link it to the tail of the merged list, and moving the current pointer of that list one step forward.
• You keep doing this while there are some remaining elements in both the lists.
• If there are still some elements in only one of the lists, you link this remaining list to the tail of the merged list.
• Initially, the merged linked list is NULL.
• Compare the value of the first two nodes and make the node with the smaller value the head node of the merged linked list.
• Since it’s the first and only node in the merged list, it will also be the tail.
• Then move head1 one step forward.

Time Complexity O(n+m)

Space Complexity O(n+m) this is auxiliary stack space due to recursion.

Code

Recursive Approach

var mergeTwoLists = function (l1, l2) {
		if(l1 == null){
			return l2;
		}
		
		if(l2 == null){
			return l1;
		} 
		
	
		if(l1.val <= l2.val){
			l1.next = mergeTwoLists(l1.next, l2);
			return l1;
		}
		else {
			l2.next = mergeTwoLists(l1, l2.next);
			return l2;            
		}

};

Iterative Approach

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let dummy = new ListNode();
    let current = dummy;
    while(list1 && list2){

        if (list1.val > list2.val){
            current.next = list2;
            current = current.next;
            list2 = list2.next;
        }
        else{
            current.next = list1;
            current = current.next;
            list1 = list1.next;
        }
    }
    if (!list1){
        current.next = list2;
    }
    if (!list2){
        current.next = list1;
    }
    return dummy.next;
    
};