Skip to main content

0021 - Merge Two Sorted Lists (Easy)

Problem Statement

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]


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

Approach 1: Recursion

Let's think of the edge cases first. If either list is null, there is no way to merge. Therefore we simply return the non-null list. In other words, if list1 is null, we return list2, and vice versa.

We compare a node in list1 and that in list2. If the value of node in list1 is smaller than that in list2, then we can set the next node to the result of next merge result. Otherwise, we set it in list2.

In general, we will have list1[0]+mergeTwoLists(list1[1:],list2)list1[0] + mergeTwoLists(list1[1:], list2) for list1[0]<list2[0]list1[0] < list2[0] else we have list2[0]+mergeTwoLists(list1,list2[1:])list2[0] + mergeTwoLists(list1, list2[1:]).

Written by @wingkwong
class Solution {
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr) return list2;
else if (list2 == nullptr) return list1;
else if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list2->next, list1);
return list2;

Approach 2: Iterative

We create a head and tail pointer.

The head pointer is created so that we can keep track of the beginning element of our list and return it in O(1)O(1) Firstly we check if either of the linked list list1list1 or list2list2 is empty if it is then we simply return the non-empty list Now we compare the first element of both the list in order to find out our beginning element of the merged linked list We set head and tail pointer to the above-obtained element and increase the list1list1 or list2list2 pointer to the next element accordingly.

Now, we run a while loop until any of the list terminates.

Case 1: if the list1list1 value is less than l2: then we shift our tail pointer to list1list1 and set tail as the current list1list1 now we shift our l1 pointer to the next element of that list.

Case 2: if the list2list2 value is less than list1list1: then we shift our tail pointer to list2list2 and set tail as the current list2list2 now we shift our list2list2 pointer to the next element of that list.

Now when these list list1list1 and list2list2 are of equal length then the while loop will terminate before traversing whole list To handle such cases we will check which list got terminated.

For example, if list1list1 is null right now then we just shift our tail pointer to the current element of list2list2 and copy the remaining element of list2list2.

As we are already having a sorted merged list, hence all the remaining elements will be greater than the largest of our current merged list. So we can just copy the remaining list.

Written by @ganajayant
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode ll = new ListNode();
ListNode tail = ll;

while (list1 != null && list2 != null) {
if (list1.val < list2.val) { = list1;
list1 =;
} else { = list2;
list2 =;
tail =;

if (list1 != null) { = list1;
tail =;

else if (list2 != null) { = list2;
tail =;