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

Merge the two lists in a 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.

&nbsp;
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]


&nbsp;
Constraints:


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


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        while list1 and list2:               
            if list1.val < list2.val:
                cur.next = list1
                list1, cur = list1.next, list1
            else:
                cur.next = list2
                list2, cur = list2.next, list2
                
        if list1 or list2:
            cur.next = list1 if list1 else list2
            
        return dummy.next
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2)
    {
        if(list1==null && list2==null)
            return null;
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;

        ListNode newHead = new ListNode();
        ListNode newNode = newHead;

        while(list1!=null && list2!=null)
        {
            //ListNode newNode = new ListNode();
            if(list1.val <= list2.val)
            {
                newNode.next = list1;
                list1 = list1.next;
            }
            else if(list1.val >= list2.val)
            {
                newNode.next = list2;
                list2 = list2.next;
            }
            newNode = newNode.next;
        }
        if(list1!=null)
            newNode.next = list1;
        else if(list2!=null)
            newNode.next = list2;
        return newHead.next;
    }
}
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(INT_MIN);
        ListNode *tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};
/**
 * 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) {

    if(!list1) return list2
    if(!list2) return list1

    let mergedList = new ListNode(0);
    let ptr = mergedList;
    let curr1 = list1;
    let curr2 = list2;

    while(curr1 && curr2){

        let newNode = new ListNode();
        if(!curr2 || curr1.val < curr2.val){
            newNode.val = curr1.val;
            newNode.next = null;
            ptr.next = newNode
            curr1 =curr1.next;
        } else{
            newNode.val = curr2.val;
            newNode.next = null;
            ptr.next = newNode
            curr2 =curr2.next;
        }

        ptr = ptr.next
    }

    if(curr1 !== null){
        ptr.next = curr1;
        curr1 = curr1.next;
    }

    if(curr2 !== null){
        ptr.next = curr2;
        curr2 = curr2.next;
    }

    return mergedList.next
};
Merge Two Sorted Lists