21. Merge Two Sorted Lists LeetCode Solution

In this guide we will provide 21. Merge Two Sorted Lists LeetCode Solution with best time and space complexity. The solution to Merge Two Sorted Lists problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Merge Two Sorted Lists solution in C++
Merge Two Sorted Lists soution in Java
Merge Two Sorted Lists solution Python
Additional Resources

21. Merge Two Sorted Lists LeetCode Solution image

Problem Statement of Merge Two Sorted Lists

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.

Complexity Analysis

Time Complexity: O(|\texttt{list1}| + |\texttt{list2}|))
Space Complexity: O(1)

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

class Solution {
 public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (!list1 || !list2)
      return list1 ? list1 : list2;
    if (list1->val > list2->val)
      swap(list1, list2);
    list1->next = mergeTwoLists(list1->next, list2);
    return list1;
  }
};
/* code provided by PROGIEZ */

21. Merge Two Sorted Lists LeetCode Solution in Java

class Solution {
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null)
      return list1 == null ? list2 : list1;
    if (list1.val > list2.val) {
      ListNode temp = list1;
      list1 = list2;
      list2 = temp;
    }
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
}
// code provided by PROGIEZ

21. Merge Two Sorted Lists LeetCode Solution in Python

class Solution:
  def mergeTwoLists(
      self,
      list1: ListNode | None,
      list2: ListNode | None,
  ) -> ListNode | None:
    if not list1 or not list2:
      return list1 if list1 else list2
    if list1.val > list2.val:
      list1, list2 = list2, list1
    list1.next = self.mergeTwoLists(list1.next, list2)
    return list1
 #code by PROGIEZ