Merge Two Sorted Lists Problem Solution

Merge Two Sorted Lists Problem: 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.

Example :

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

Merge Two Sorted Lists Problem Solution

Problem Solution In Python

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        prehead = ListNode(-1)

        curr = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next            
            curr = curr.next

        if l1 is not None:
            curr.next = l1
        else:
            curr.next = l2

        return prehead.next

Problem Solution In Java

class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode tmp = new ListNode(0);
        ListNode start = tmp;
        
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                tmp.next = new ListNode(l2.val);
                tmp = tmp.next;
                l2 = l2.next;
            } else if (l2 == null) {
                tmp.next = new ListNode(l1.val);
                tmp = tmp.next;
                l1 = l1.next;
            } else {
                if (l1.val < l2.val) {
                    tmp.next = new ListNode(l1.val);                    
                    tmp = tmp.next;
                    l1 = l1.next;
                } else {
                    tmp.next = new ListNode(l2.val);
                    tmp = tmp.next;
                    l2 = l2.next;
                }
            }
        }
        
        return start.next;
    }
}

Problem Solution In C++

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* head = NULL;
    struct ListNode* p= NULL;
    
    if(!l1){
        return l2;
    }
    if(!l2){
        return l1;
    }
    
    if(l2->val > l1->val){
        head = p = l1;
        l1 = l1->next;
    }
    else{
        head = p = l2;
        l2 = l2->next;
    }
    
    while(l1 && l2){
       if(l1->val > l2->val){
           p->next = l2;
           p = l2;
           l2 = l2->next;
       } 
       else{
           p->next = l1;
           p = l1;
           l1 = l1->next;
       }
    }
    
    if(l1){
        p->next = l1;
    }
    
    if(l2){
        p->next = l2;
    }
    
    
    return head;
}

Problem Solution In C

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l2==NULL)
        return l1;
    else if(l1==NULL)
        return l2;
    if(l1->val<=l2->val){
        l1->next=mergeTwoLists(l1->next,l2);
        return l1;
     }
    else {
        l2->next=mergeTwoLists(l1,l2->next);
        return l2;
    }
}