What is the time complexity of Merge Two Sorted Lists?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Merge Two Sorted Lists?

This problem uses Linked List, Recursion. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Merge Two Sorted Lists?

**The Dummy Node Tactic:** Using a `dummy` node as a head placeholder for the merged list simplifies initial node placement. It ensures `tail` always points to a valid node, even when the merged list is empty, allowing a consistent `tail.next = ...` operation without needing to check if `head` is null. **Greedy Iterative Splicing:** The core idea is to iteratively compare the heads of the remaining `list1` and `list2`, 'greedily' appending the smaller node to the end of our growing merged list. We then advance *only* the pointer of the list from which we took the node, ensuring we always consider the smallest available element for the next step.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Merge Two Sorted Lists - LeetCode 21 Solution

Q: How to solve Merge Two Sorted Lists?

The provided solution employs an elegant iterative approach using a 'dummy' node and a 'tail' pointer. We initialize a `dummy` node (its value doesn't matter, it's just a placeholder) and a `tail` pointer, which initially points to `dummy`. This `dummy` node is a common trick in linked list problems; it simplifies the logic by giving us a consistent node to attach new elements to, avoiding special-casing when the merged list is empty. We then enter a loop that continues as long as both `list1` and `list2` have nodes. Inside the loop, we compare the `val` of the current nodes in `list1` and `list2`. The node with the smaller value is appended to `tail.next`, and then the pointer of the list from which that node was taken is advanced (`list1 = list1.next` or `list2 = list2.next`). Regardless of which node was chosen, `tail` is then advanced to point to the newly appended node, preparing for the next attachment. Once one of the lists becomes empty, the loop terminates. At this point, the *entire remainder* of the other list (if any) is already sorted and simply needs to be appended to the `tail` of our merged list. Finally, we return `dummy.next`, as `dummy` itself was just a starting placeholder.

Q: Which companies ask LeetCode 21. Merge Two Sorted Lists in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Arista Networks, Bloomberg and 34 more companies.

Merge Two Sorted Lists - Complete Solution Guide

Merge Two Sorted Lists is LeetCode problem 21, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

You're presented with two linked lists, `list1` and `list2`, both already sorted in non-decreasing order. The task isn't just to combine them, but to interweave their nodes to form a *single, new* sorted linked list. Crucially, the problem specifies 'splicing together the nodes,' implying we should reuse the existing nodes rather than creating entirely new ones and copying values over. Think of it like merging two sorted decks of cards into one sorted deck, carefully picking the lowest card available from either pile at each step.

Solution Approach

The provided solution employs an elegant iterative approach using a 'dummy' node and a 'tail' pointer. We initialize a `dummy` node (its value doesn't matter, it's just a placeholder) and a `tail` pointer, which initially points to `dummy`. This `dummy` node is a common trick in linked list problems; it simplifies the logic by giving us a consistent node to attach new elements to, avoiding special-casing when the merged list is empty. We then enter a loop that continues as long as both `list1` and `list2` have nodes. Inside the loop, we compare the `val` of the current nodes in `list1` and `list2`. The node with the smaller value is appended to `tail.next`, and then the pointer of the list from which that node was taken is advanced (`list1 = list1.next` or `list2 = list2.next`). Regardless of which node was chosen, `tail` is then advanced to point to the newly appended node, preparing for the next attachment. Once one of the lists becomes empty, the loop terminates. At this point, the *entire remainder* of the other list (if any) is already sorted and simply needs to be appended to the `tail` of our merged list. Finally, we return `dummy.next`, as `dummy` itself was just a starting placeholder.

Step-by-Step Algorithm

Step 1: Create a dummy node and initialize a tail pointer to it. This dummy node simplifies handling the head of the merged list.
Step 2: Iterate while both `list1` and `list2` are not empty. Compare the values of the current nodes in `list1` and `list2`.
Step 3: Append the node with the smaller value to the tail of the merged list by setting `tail.next` to that node. Then, advance the pointer of the list from which the node was taken.
Step 4: Update the tail pointer to point to the newly added node.
Step 5: After one of the lists is empty, append the remaining nodes from the other list to the tail of the merged list.
Step 6: Return the `next` of the dummy node (the actual head of the merged list).

Key Insights

**The Dummy Node Tactic:** Using a `dummy` node as a head placeholder for the merged list simplifies initial node placement. It ensures `tail` always points to a valid node, even when the merged list is empty, allowing a consistent `tail.next = ...` operation without needing to check if `head` is null.
**Greedy Iterative Splicing:** The core idea is to iteratively compare the heads of the remaining `list1` and `list2`, 'greedily' appending the smaller node to the end of our growing merged list. We then advance *only* the pointer of the list from which we took the node, ensuring we always consider the smallest available element for the next step.
**Efficient Remainder Appending:** Once one input list is exhausted, the entire remaining portion of the other list can be appended directly to the end of the merged list in a single step (`tail.next = list1` or `tail.next = list2`). This works because the remaining list is already sorted, and there are no more elements from the other list to interleave with it.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Recursion.

Companies

Asked at: Adobe, Amazon, Apple, Arista Networks, Bloomberg, Capital One, Cognizant, EPAM Systems, Flipkart, Goldman Sachs, HPE, Huawei, Hubspot, Infosys, Intel, Intuit, LinkedIn, Media.net, Meta, Microsoft, Oracle, Palo Alto Networks, Revolut, Rippling, Shopee, Siemens, Snap, Snowflake, Swiggy, Teradata, Texas Instruments, TikTok, Uber, Visa, Walmart Labs, Wix, Yahoo, Yandex, tcs.

Merge Two Sorted Lists | LeetCode 21

Easy

Linked List Recursion

Time: O(n)Space: O(1)

Solution Code

Available in:

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;

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

        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }

        return dummy.next;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 21: Merge Two Sorted Lists - Detailed explanation and solution approaches.

Topics

Linked List Recursion

Companies

AdobeAmazonAppleArista NetworksBloombergCapital OneCognizantEPAM Systems

Stats

Difficulty:Easy

Languages:4

Companies:39

Problem #:21

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Create a dummy node and initialize a tail pointer to it. This dummy node simplifies handling the head of the merged list.
2
Step 2: Iterate while both `list1` and `list2` are not empty. Compare the values of the current nodes in `list1` and `list2`.
3
Step 3: Append the node with the smaller value to the tail of the merged list by setting `tail.next` to that node. Then, advance the pointer of the list from which the node was taken.
4
Step 4: Update the tail pointer to point to the newly added node.
5
Step 5: After one of the lists is empty, append the remaining nodes from the other list to the tail of the merged list.
6
Step 6: Return the `next` of the dummy node (the actual head of the merged list).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The while loop iterates a maximum of m + n times, where m and n are the lengths of the input lists. All other operations take constant time. No extra space proportional to the input size is used beyond the pointers.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach

Recursively compare the heads of the lists. The smaller head is added to the merged list and the function recursively calls itself with the next node of the list that provided the smaller head and the other list.

Time: O(m + n)Space: O(m + n) in the worst case due to recursive call stack depth. Could be O(min(m,n)) in average case.

Trade-offs: The recursive approach can be less efficient than the iterative approach due to the overhead of recursive calls, especially for very large lists. The iterative approach generally has better space complexity.

✨

Key Insights

1**The Dummy Node Tactic:** Using a `dummy` node as a head placeholder for the merged list simplifies initial node placement. It ensures `tail` always points to a valid node, even when the merged list is empty, allowing a consistent `tail.next = ...` operation without needing to check if `head` is null.
2**Greedy Iterative Splicing:** The core idea is to iteratively compare the heads of the remaining `list1` and `list2`, 'greedily' appending the smaller node to the end of our growing merged list. We then advance *only* the pointer of the list from which we took the node, ensuring we always consider the smallest available element for the next step.
3**Efficient Remainder Appending:** Once one input list is exhausted, the entire remaining portion of the other list can be appended directly to the end of the merged list in a single step (`tail.next = list1` or `tail.next = list2`). This works because the remaining list is already sorted, and there are no more elements from the other list to interleave with it.

📚

Key Terms Explained

For Students

Recursion

A function that calls itself to solve smaller versions of the same problem.

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: One or both input lists are empty. The solution correctly handles this by checking for `null` (or `None` in Python) pointers and appending the non-empty list to the dummy node.
Edge case 2: Lists have different lengths. The solution naturally handles this because the while loop terminates when one list is exhausted, and the remaining nodes from the other list are appended.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the empty list cases. The algorithm must correctly merge even when one or both input lists are empty.

✗Common mistake 2: Incorrectly handling the `next` pointers during the merging process. Failure to update the `next` pointers correctly will result in an incorrect or broken linked list.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Merging sorted data streams. Imagine two systems generating sorted data; this algorithm can efficiently combine these streams into a single sorted stream.

🏦Real-world scenario 2: Efficiently combining results from multiple sorted searches. In a database system, multiple sorted indexes might need to be combined – this algorithm provides a way to do this efficiently.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

How does the fast/slow pointer technique work?

Fast pointer moves 2 steps while slow moves 1 step. When fast reaches the end, slow is at middle. If there's a cycle, they will meet. This technique is used for: finding middle node, detecting cycles, finding cycle start point, and checking palindromes.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Merge Two Sorted Lists"?

For this easy-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether recursion techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?