Merge Two Sorted Lists

Solution

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.

 

Examples

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.

Explanation

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newNode = new ListNode(0);
        ListNode currNode = newNode;
        
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                currNode.next = list1;
                list1 = list1.next;
            }else{
                currNode.next = list2;
                list2 = list2.next;
            }
            currNode = currNode.next;   
        }
        
        if(list1 != null){
            currNode.next = list1;
            list1 = list1.next;
        }
        
        if(list2 != null){
            currNode.next = list2;
            list2 = list2.next;
        }
        
        return newNode.next;
        
    }
}

 

newNode: It is a dummy node and created with an arbitrary value (0 in this case) to make managing the merged list simpler.

currNode: It is initialized to point to newNode. It will move through the new list as nodes are added.

 

A while loop runs as long as both list1 and list2 are non-null.

Inside this loop, if list1's current value is smaller than list2's, currNode.next is set to list1's current node, and list1 moves to its next node. Otherwise, currNode.next is set to list2's current node, and list2 moves to its next node. currNode is then updated to its next node in the new merged list, effectively adding the selected node to the merged list.

 

After exiting the while loop, if either list1 or list2 still has nodes left, they are already sorted, so we attach the remaining nodes to currNode.next.

 

Finally, the merged list starts at newNode.next since newNode is just a dummy. This merged list is returned.