In this post, we are going to solve the 21. Merge Two Sorted Lists problem of Leetcode. This problem 21. Merge Two Sorted Lists is a Leetcode easy level problem. Let’s see the code, 21. Merge Two Sorted Lists – Leetcode Solution.

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 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.

Now, let’s see the code of 21. Merge Two Sorted Lists – Leetcode Solution.

Merge Two Sorted Lists – Leetcode Solution

21. Merge Two Sorted Lists – Solution in Java

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Java Programming Language.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode handler = head;
        while(l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                handler.next = l1;
                l1 = l1.next;
            } else {
                handler.next = l2;
                l2 = l2.next;
            }
            handler = handler.next;
        }
        
        if (l1 != null) {
            handler.next = l1;
        } else if (l2 != null) {
            handler.next = l2;
        }
        
        return head.next;
    }
}

Now let’s see the Recursive approach to solve the same problem in Java using Recursion.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        ListNode handler;
        if(l1.val < l2.val) {
            handler = l1;
            handler.next = mergeTwoLists(l1.next, l2);
        } else {
            handler = l2;
            handler.next = mergeTwoLists(l1, l2.next);
        }
        
        return handler;
    }
}

21. Merge Two Sorted Lists – Solution in C++

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in C++ Programming Language.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
       ListNode* temp = new ListNode(-1);
        ListNode* head = temp;
        while(l1!=NULL and l2!=NULL){
            if(l1->val<=l2->val){
                head->next = l1;
                l1 = l1->next;
            }
            else {
                head->next = l2;
                l2 = l2->next;
            }
            head=head->next;
        }
        if(l1!=NULL)
        {
            head->next = l1;
        }
        else head->next = l2;
        
        return temp->next;
    }
};

Now let’s see the Recursive approach to solve the same problem in C++ using Recursion.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* 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;            
		}
	}
};	

21. Merge Two Sorted Lists – Solution in Python

This is the Iterative Approach to the solution of 21. Merge Two Sorted Lists in Python Programming Language.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def mergeTwoLists1(self, l1, l2):
    dummy = cur = ListNode(0)
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

Now let’s see the Recursive approach to solve the same problem in Python using Recursion.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def mergeTwoLists2(self, l1, l2):
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2

Note: This problem 21. Merge Two Sorted Lists is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.