Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Merge Two Sorted Lists solution and explanation

EasyLinked ListRecursion8 min read68.7% acceptanceUpdated 9 Apr 2026
Asked atHpeWixHuaweiUdemyBloombergAccenture
+14 moreDocuSignHubSpotGoogleAmazonMicrosoftMetaAppleInfosysYandexSnowflakeServiceNowArista NetworksJosh TechnologyCapgemini
Practise Merge Two Sorted Lists
6:16
Merge Two Sorted Lists - Leetcode 21 - PythonNeetCode · 6:16 · 550K viewsWatch on YouTube
9 more videos on this problem
  1. Merge Two Sorted Lists - Leetcode 21 - PythonNeetCode · 6:16 · 550K views
  2. LeetCode Merge Two Sorted Lists Solution Explained - JavaNick White · 4:03 · 136K views
  3. Merge Two Sorted Linked Lists (LeetCode 21) | Full solution with Examples | Study AlgorithmsNikhil Lohia · 7:01 · 58K views
  4. Merge Two Sorted Lists | Live Coding with Explanation | Leetcode #21Algorithms Made Easy · 4:30 · 51K views
  5. LeetCode 21: Merge Two Sorted Lists (Visualization)Abstracted Away · 3:48 · 39K views
  6. Merge Two Sorted Lists - Leetcode 21 - Linked Lists (Python)Greg Hogg · 9:41 · 39K views
  7. LeetCode 21: Merge Two Sorted Lists RECURSIVELY - Interview Prep Ep 62Fisher Coder · 12:38 · 30K views
  8. Merge Two Sorted Lists | LeetCode 21 | Amazon Coding Interview TutorialTerrible Whiteboard · 11:55 · 12K views
  9. Merge Two Sorted Lists - LeetCode 21 - JavaScriptAlgoJS · 4:11 · 5K views
  10. LeetCode 21: Merge Two Sorted Lists ITERATIVELY - Interview Prep Ep 61Fisher Coder · 11:50 · 4K views

The problem

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.

Approach overview

Problem Overview: You receive the heads of two sorted singly linked lists. The task is to merge them into one sorted list by reusing the existing nodes. The result must preserve the sorted order while traversing each list only as needed.

Approach 1: Iterative Approach Using a Dummy Node (O(n + m) time, O(1) space)

This approach walks through both lists simultaneously and builds the merged list step by step. A dummy node is created at the start to simplify pointer manipulation. Two pointers compare the current nodes from each list, and the smaller node is appended to the merged list. Then the pointer of the list that contributed the node moves forward. Once one list is exhausted, the remaining nodes from the other list are attached directly since they are already sorted.

The key insight is that you never need to create new nodes or perform extra sorting. You simply relink the existing nodes while iterating through them once. Because each node is visited exactly once, the time complexity is O(n + m), where n and m are the lengths of the two lists. The algorithm uses O(1) additional space since it only maintains a few pointers. This is the most common solution when working with linked list merge operations.

Approach 2: Recursive Approach (O(n + m) time, O(n + m) space)

The recursive strategy relies on the observation that the merged list's head must be the smaller of the two current nodes. Compare list1.val and list2.val. The smaller node becomes the head, and its next pointer is set to the result of merging the remaining part of that list with the other list. This naturally breaks the problem into smaller subproblems until one list becomes empty.

If either list reaches null, the remaining list can be returned directly because it is already sorted. Each recursive call processes one node, leading to a total time complexity of O(n + m). However, recursion uses the call stack, which adds O(n + m) space in the worst case. This pattern is common when solving recursion problems on linked structures because the structure itself mirrors the recursive calls.

Recommended for interviews: Interviewers typically expect the iterative dummy node solution. It demonstrates strong pointer manipulation skills and keeps memory usage at O(1). The recursive version is elegant and concise, but the iterative approach shows better control over linked list operations and avoids stack overhead. Many candidates start by describing the recursive logic conceptually, then implement the iterative version for optimal space usage.

Approach 1: Iterative Approach Using a Dummy Node

This approach involves using a dummy node to ease the merging process. A dummy node is a temporary node that helps in easily managing edge cases such as initializing the result list and returning the correct head of the list. We will iterate over both lists, and in each iteration, we'll add the smallest current node to our result list. The time complexity of this method is O(n + m), where n and m are the lengths of the two lists.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        tail = dummy
        
        while l1 and 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 if l1 else l2

        return dummy.next
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = l1 != null ? l1 : l2;

        return dummy.next;
    }
}
#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        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;
    }
};
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function mergeTwoLists(l1, l2) {
    let dummy = new ListNode(0);
    let tail = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 !== null ? l1 : l2;

    return dummy.next;
}
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;
    
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    tail->next = list1 ? list1 : list2;
    return dummy.next;
}
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        tail.next = l1 ?? l2;

        return dummy.next;
    }
}

The Python code uses a dummy node to merge the two input lists iteratively. The merging process involves a while loop that continues as long as there are nodes in both lists. During each loop iteration, the node with the smaller value is appended to the result list. The 'tail' keeps track of the end of the merged list. Once the loop concludes, any remaining nodes of the non-empty list are appended to the result. The code ultimately returns the next node after the dummy to represent the merged list's head.

Complexity

Time Complexity: O(n + m), where n and m are the lengths of list1 and list2.
Space Complexity: O(1), given that the list is modified in place.

Try this approach in the editor

Approach 2: Recursive Approach

The recursive approach simplifies merging by using recursive function calls to naturally handle merging nodes. This method leverages the call stack to handle the comparisons and merging order, with each function call processing pairwise comparisons when identifying the next node for the merged list. The recursion terminates when either list is fully traversed, thereby appending the remainder of the other list if needed. The recursive nature implicitly manages the combination of currently smallest nodes. The complexity is linear relative to the combined size of the lists.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1

        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
public 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;
        }
    }
}
#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;

        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};
function mergeTwoLists(l1, 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;
    }
}
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val <= l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}
public 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;
        }
    }
}

In this Python recursive approach, the method 'mergeTwoLists' compares given list node values, linking the smaller node's 'next' to a recursive solution call for merging subsequent nodes. The base cases terminate recursion upon either list being entirely consumed, subsequently returning the unfinished segment of the other list. The layered recursion accumulates connections consistently, preserving ordered node merging reflective of merging sorted lists.

Complexity

Time Complexity: O(n + m), representing node processing for both lists.
Space Complexity: O(n + m), as recursive call stack depth correlates with total node count.

Try this approach in the editor

Approach 3: Recursion

First, we judge whether the linked lists l_1 and l_2 are empty. If one of them is empty, we return the other linked list. Otherwise, we compare the head nodes of l_1 and l_2:

  • If the value of the head node of l_1 is less than or equal to the value of the head node of l_2, we recursively call the function mergeTwoLists(l_1.next, l_2), and connect the head node of l_1 with the returned linked list head node, and return the head node of l_1.
  • Otherwise, we recursively call the function mergeTwoLists(l_1, l_2.next), and connect the head node of l_2 with the returned linked list head node, and return the head node of l_2.

The time complexity is O(m + n), and the space complexity is O(m + n). Here, m and n are the lengths of the two linked lists respectively.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if (list1 == null || list2 == null) {
        return list1 || list2;
    }
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val <= list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	} else {
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	}
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn merge_two_lists(
        list1: Option<Box<ListNode>>,
        list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        match (list1, list2) {
            (None, None) => None,
            (Some(list), None) => Some(list),
            (None, Some(list)) => Some(list),
            (Some(mut list1), Some(mut list2)) => {
                if list1.val < list2.val {
                    list1.next = Self::merge_two_lists(list1.next, Some(list2));
                    Some(list1)
                } else {
                    list2.next = Self::merge_two_lists(Some(list1), list2.next);
                    Some(list2)
                }
            }
        }
    }
}
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
    if list1.nil?
        return list2
    end
    if list2.nil?
        return list1
    end
    if list1.val <= list2.val
        list1.next = merge_two_lists(list1.next, list2)
        return list1
    else
        list2.next = merge_two_lists(list1, list2.next)
        return list2
    end
end
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        if (is_null($list1)) {
            return $list2;
        }
        if (is_null($list2)) {
            return $list1;
        }
        if ($list1->val <= $list2->val) {
            $list1->next = $this->mergeTwoLists($list1->next, $list2);
            return $list1;
        } else {
            $list2->next = $this->mergeTwoLists($list1, $list2->next);
            return $list2;
        }
    }
}
Try this approach in the editor

Approach 4: Iteration

We can also use iteration to implement the merging of two sorted linked lists.

First, we define a dummy head node dummy, then loop through the two linked lists, compare the head nodes of the two linked lists, add the smaller node to the end of dummy, until one of the linked lists is empty, then add the remaining part of the other linked list to the end of dummy.

Finally, return dummy.next.

The time complexity is O(m + n), where m and n are the lengths of the two linked lists respectively. Ignoring the space consumption of the answer linked list, the space complexity is O(1).

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0);
    let cur = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    cur.next = list1 || list2;
    return dummy.next;
}
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{}
	curr := dummy
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			curr.Next = list1
			list1 = list1.Next
		} else {
			curr.Next = list2
			list2 = list2.Next
		}
		curr = curr.Next
	}
	if list1 != nil {
		curr.Next = list1
	} else {
		curr.Next = list2
	}
	return dummy.Next
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn merge_two_lists(
        mut list1: Option<Box<ListNode>>,
        mut list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut new_list = ListNode::new(0);
        let mut cur = &mut new_list;
        while list1.is_some() && list2.is_some() {
            let (l1, l2) = (list1.as_deref_mut().unwrap(), list2.as_deref_mut().unwrap());
            if l1.val < l2.val {
                let next = l1.next.take();
                cur.next = list1.take();
                list1 = next;
            } else {
                let next = l2.next.take();
                cur.next = list2.take();
                list2 = next;
            }
            cur = cur.next.as_deref_mut().unwrap();
        }
        cur.next = list1.or(list2);
        new_list.next
    }
}
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
    dummy = ListNode.new()
    cur = dummy
    while list1 && list2
        if list1.val <= list2.val
            cur.next = list1
            list1 = list1.next
        else
            cur.next = list2
            list2 = list2.next
        end
        cur = cur.next
    end
    cur.next = list1 || list2
    dummy.next
end
# Definition for singly-linked list.
# class ListNode {
#     public $val;
#     public $next;
#     public function __construct($val = 0, $next = null)
#     {
#         $this->val = $val;
#         $this->next = $next;
#     }
# }
class Solution {
    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        $dummy = new ListNode(0);
        $current = $dummy;
        while ($list1 != null && $list2 != null) {
            if ($list1->val <= $list2->val) {
                $current->next = $list1;
                $list1 = $list1->next;
            } else {
                $current->next = $list2;
                $list2 = $list2->next;
            }
            $current = $current->next;
        }
        if ($list1 != null) {
            $current->next = $list1;
        } elseif ($list2 != null) {
            $current->next = $list2;
        }
        return $dummy->next;
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Iterative Approach Using a Dummy Node

Time Complexity: O(n + m), where n and m are the lengths of list1 and list2.
Space Complexity: O(1), given that the list is modified in place.

Recursive Approach

Time Complexity: O(n + m), representing node processing for both lists.
Space Complexity: O(n + m), as recursive call stack depth correlates with total node count.

Recursion–
Iteration–

Complexity analysis

ApproachTimeSpaceWhen to Use
Iterative with Dummy NodeO(n + m)O(1)Best general solution; preferred in interviews due to constant extra space
Recursive MergeO(n + m)O(n + m)When recursion is acceptable and you want a concise, expressive solution

Frequently asked questions

Is Merge Two Sorted Lists easy or hard?

Merge Two Sorted Lists is categorized as an Easy problem on most coding platforms. The logic is straightforward once you understand pointer movement in linked lists, making it a common introductory interview problem.

Merge Two Sorted Lists Python/Java solution

Python and Java implementations typically follow the same logic: iterate through both lists, compare current node values, and attach the smaller node to the merged list. Both iterative and recursive versions achieve O(n + m) time complexity.

How to solve Merge Two Sorted Lists in O(n)?

Traverse both lists simultaneously and always attach the smaller node to the result list. Using a dummy head node simplifies the implementation. Because every node from both lists is processed exactly once, the total complexity becomes O(n + m).

What is the best approach for Merge Two Sorted Lists?

The iterative dummy node approach is generally considered the best solution. It merges the two lists in O(n + m) time while using only O(1) extra space. The dummy node simplifies pointer updates and avoids edge cases when initializing the merged list.

Is Merge Two Sorted Lists asked at Google/Amazon/Meta?

Merge Two Sorted Lists appears frequently in coding interviews at companies like Amazon, Google, and Meta. It tests understanding of linked list traversal, pointer manipulation, and algorithmic efficiency using linear-time merging.

What data structure is used in Merge Two Sorted Lists?

The problem uses a singly linked list. The algorithm relies on pointer manipulation to compare nodes from two lists and reconnect them into a single sorted linked list without creating additional data structures.

What is the time complexity of Merge Two Sorted Lists?

The optimal time complexity is O(n + m), where n and m are the lengths of the two linked lists. Each node is visited exactly once while comparing and linking nodes into the final merged list.

Comments

Next problem · similarMerge k Sorted ListsHard
Now write it yourselfClose this page and solve Merge Two Sorted Lists in the editor, without looking.
Practise Merge Two Sorted Lists