Jobs

Interviews

Discussions

Merge Two Sorted Lists #10 Most Asked

Easy

Capgemini

1 view

Topics:

Linked ListsRecursion

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.

Try coding it in LeetCode

Merge Two Sorted Lists #10 Most Asked

Easy

Capgemini

1 view

Topics:

Linked ListsRecursion

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should be the return value if one or both of the input lists are empty?
What is the range of values the nodes can contain, for example, can they be negative or zero?
Are the input lists sorted in ascending or descending order?
How should I handle duplicate values that might exist within a single list or across both lists?
Are there any constraints on the number of nodes in each list that I should be aware of?

Brute Force Solution

Approach

The simplest way to solve this is to first gather all the items from both lists into one single, large collection. Then, sort this combined collection from the smallest item to the largest to get the final merged list.

Here's how the algorithm would work step-by-step:

First, create a brand new, empty collection.
Go through the first sorted list and add every single item from it into your new collection.
Next, go through the second sorted list and also add all of its items to that same new collection.
At this point, you have one big collection holding everything, but it's not in order yet.
Now, take this big collection and rearrange all the items within it from the smallest to the largest value.
Finally, take this newly sorted collection and build the final, properly ordered list from it.

Code Implementation

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

def mergeTwoLists(list_one: ListNode, list_two: ListNode) -> ListNode:
    all_values = []

    current_node = list_one
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    current_node = list_two
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    # Sorting is necessary because the collection has values from both lists but is not ordered.

    all_values.sort()

    # A dummy head node simplifies building the new list by providing a fixed starting point.

    head_of_merged_list = ListNode()
    current_merged_node = head_of_merged_list

    # We must iterate through the sorted values to construct the final linked list in order.

    for value in all_values:
        current_merged_node.next = ListNode(value)
        current_merged_node = current_merged_node.next

    return head_of_merged_list.next

Big(O) Analysis

Time Complexity

O(n log n) – The primary cost of this approach comes from the sorting step. Let n be the total number of nodes in both lists combined. First, we iterate through both lists to gather all n nodes into a single collection, which takes O(n) time. The most significant operation is then sorting this collection of n items, which typically has a time complexity of O(n log n) using an efficient sorting algorithm like mergesort or quicksort. Finally, rebuilding the linked list from the sorted collection takes another O(n) time, but the sorting step dominates the overall complexity, making it O(n log n).

Space Complexity

O(N) – The algorithm first creates a new, large collection to hold all items from both input lists. If the first list has M elements and the second has L elements, this new collection will require space to store all M + L items. We define N as the total number of elements (N = M + L), so this step creates an auxiliary data structure of size N. Additionally, the sorting algorithm used on this collection might require its own auxiliary space, which is typically O(log N) or O(N) depending on the implementation, but the O(N) space for the collection itself is the dominant factor.

Optimal Solution

Approach

The best way to solve this is to build a new, single sorted list by picking the smaller of the two front items from the original lists, one by one. This way, we always add the next smallest available item to our new list, guaranteeing it stays sorted without extra work.

Here's how the algorithm would work step-by-step:

Imagine you have two lines of people, each sorted by height from shortest to tallest.
To create a new single sorted line, start by looking at the first person in each of the two lines.
Compare these two people and ask the shorter one to step into your new line.
Now, look at the person who just moved and the person at the front of the other line.
Again, pick the shorter of these two and have them be the next person in the new line.
Continue this process of comparing the front person from each original line and moving the shorter one to the end of your new line.
If one of the original lines becomes empty, you don't need to compare anymore. Simply have everyone from the remaining line join the new line in their current order.
By repeating this simple choice, you will have built a single, perfectly sorted line containing everyone from the first two lines.

Code Implementation

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

def mergeTwoLists(list_one, list_two):
    # Create a dummy node to act as the starting point of the merged list.

    dummy_head_node = ListNode()
    current_merged_node = dummy_head_node

    while list_one and list_two:
        # Compare the front nodes of both lists to decide which one to add next.

        if list_one.val < list_two.val:
            current_merged_node.next = list_one
            list_one = list_one.next
        else:
            current_merged_node.next = list_two
            list_two = list_two.next
        
        current_merged_node = current_merged_node.next

    # If one list is exhausted, append the rest of the other list.

    if list_one:
        current_merged_node.next = list_one
    elif list_two:
        current_merged_node.next = list_two

    return dummy_head_node.next

Big(O) Analysis

Time Complexity

O(n + m) – The algorithm iterates through both lists once, comparing the head of each list at every step. In each step of the main comparison loop, we process exactly one node from either the first list (of size n) or the second list (of size m). Once one list is exhausted, the remaining nodes of the other list are appended in a single operation. Therefore, the total number of operations is directly proportional to the total number of nodes in both lists, which is n + m, simplifying to O(n + m).

Space Complexity

O(N) – The algorithm builds a completely new sorted list to store the final result. The size of this new list will be the sum of the lengths of the two original lists. Therefore, if N is the total number of nodes in both input lists, we use auxiliary space proportional to N to construct the new list. A few pointers are also used to keep track of the current positions, but their memory usage is constant and insignificant compared to the new list.

Edge Cases

Case	How to Handle
One or both of the input lists are null or empty	The solution should return the other non-empty list, or null if both are empty.
One list is exhausted while the other still has nodes	The remaining portion of the non-empty list is appended to the end of the merged list.
Both lists contain only a single node	The two nodes are compared and linked correctly to form a new two-node sorted list.
Both lists contain duplicate values, either within a list or across lists	The relative order of equal elements is preserved by the merge logic, ensuring a stable merge.
The lists contain negative numbers and zeros	The standard comparison logic correctly handles negative numbers and zeros without special cases.
One list is significantly longer than the other	The iterative approach efficiently handles this by simply appending the rest of the longer list once the shorter one is consumed.
All elements in one list are smaller than all elements in the other	The solution will effectively append the second list to the end of the first list.
Maximum-sized inputs leading to deep recursion	An iterative solution is preferred to avoid potential stack overflow errors that a naive recursive solution might face with very long lists.

One or both of the input lists are null or empty

How to Handle:

The solution should return the other non-empty list, or null if both are empty.

One list is exhausted while the other still has nodes

How to Handle:

The remaining portion of the non-empty list is appended to the end of the merged list.

Both lists contain only a single node

How to Handle:

The two nodes are compared and linked correctly to form a new two-node sorted list.

Both lists contain duplicate values, either within a list or across lists

How to Handle:

The relative order of equal elements is preserved by the merge logic, ensuring a stable merge.

The lists contain negative numbers and zeros

How to Handle:

The standard comparison logic correctly handles negative numbers and zeros without special cases.

One list is significantly longer than the other

How to Handle:

The iterative approach efficiently handles this by simply appending the rest of the longer list once the shorter one is consumed.

All elements in one list are smaller than all elements in the other

How to Handle:

The solution will effectively append the second list to the end of the first list.

Maximum-sized inputs leading to deep recursion

How to Handle:

An iterative solution is preferred to avoid potential stack overflow errors that a naive recursive solution might face with very long lists.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should be the return value if one or both of the input lists are empty?
What is the range of values the nodes can contain, for example, can they be negative or zero?
Are the input lists sorted in ascending or descending order?
How should I handle duplicate values that might exist within a single list or across both lists?
Are there any constraints on the number of nodes in each list that I should be aware of?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a brand new, empty collection.
Go through the first sorted list and add every single item from it into your new collection.
Next, go through the second sorted list and also add all of its items to that same new collection.
At this point, you have one big collection holding everything, but it's not in order yet.
Now, take this big collection and rearrange all the items within it from the smallest to the largest value.
Finally, take this newly sorted collection and build the final, properly ordered list from it.

Code Implementation

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

def mergeTwoLists(list_one: ListNode, list_two: ListNode) -> ListNode:
    all_values = []

    current_node = list_one
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    current_node = list_two
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    # Sorting is necessary because the collection has values from both lists but is not ordered.

    all_values.sort()

    # A dummy head node simplifies building the new list by providing a fixed starting point.

    head_of_merged_list = ListNode()
    current_merged_node = head_of_merged_list

    # We must iterate through the sorted values to construct the final linked list in order.

    for value in all_values:
        current_merged_node.next = ListNode(value)
        current_merged_node = current_merged_node.next

    return head_of_merged_list.next

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have two lines of people, each sorted by height from shortest to tallest.
To create a new single sorted line, start by looking at the first person in each of the two lines.
Compare these two people and ask the shorter one to step into your new line.
Now, look at the person who just moved and the person at the front of the other line.
Again, pick the shorter of these two and have them be the next person in the new line.
Continue this process of comparing the front person from each original line and moving the shorter one to the end of your new line.
If one of the original lines becomes empty, you don't need to compare anymore. Simply have everyone from the remaining line join the new line in their current order.
By repeating this simple choice, you will have built a single, perfectly sorted line containing everyone from the first two lines.

Code Implementation

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

def mergeTwoLists(list_one, list_two):
    # Create a dummy node to act as the starting point of the merged list.

    dummy_head_node = ListNode()
    current_merged_node = dummy_head_node

    while list_one and list_two:
        # Compare the front nodes of both lists to decide which one to add next.

        if list_one.val < list_two.val:
            current_merged_node.next = list_one
            list_one = list_one.next
        else:
            current_merged_node.next = list_two
            list_two = list_two.next
        
        current_merged_node = current_merged_node.next

    # If one list is exhausted, append the rest of the other list.

    if list_one:
        current_merged_node.next = list_one
    elif list_two:
        current_merged_node.next = list_two

    return dummy_head_node.next

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
One or both of the input lists are null or empty	The solution should return the other non-empty list, or null if both are empty.
One list is exhausted while the other still has nodes	The remaining portion of the non-empty list is appended to the end of the merged list.
Both lists contain only a single node	The two nodes are compared and linked correctly to form a new two-node sorted list.
Both lists contain duplicate values, either within a list or across lists	The relative order of equal elements is preserved by the merge logic, ensuring a stable merge.
The lists contain negative numbers and zeros	The standard comparison logic correctly handles negative numbers and zeros without special cases.
One list is significantly longer than the other	The iterative approach efficiently handles this by simply appending the rest of the longer list once the shorter one is consumed.
All elements in one list are smaller than all elements in the other	The solution will effectively append the second list to the end of the first list.
Maximum-sized inputs leading to deep recursion	An iterative solution is preferred to avoid potential stack overflow errors that a naive recursive solution might face with very long lists.

One or both of the input lists are null or empty

How to Handle:

The solution should return the other non-empty list, or null if both are empty.

One list is exhausted while the other still has nodes

How to Handle:

The remaining portion of the non-empty list is appended to the end of the merged list.

Both lists contain only a single node

How to Handle:

The two nodes are compared and linked correctly to form a new two-node sorted list.

Both lists contain duplicate values, either within a list or across lists

How to Handle:

The relative order of equal elements is preserved by the merge logic, ensuring a stable merge.

The lists contain negative numbers and zeros

How to Handle:

The standard comparison logic correctly handles negative numbers and zeros without special cases.

One list is significantly longer than the other

How to Handle:

The iterative approach efficiently handles this by simply appending the rest of the longer list once the shorter one is consumed.

All elements in one list are smaller than all elements in the other

How to Handle:

The solution will effectively append the second list to the end of the first list.

Maximum-sized inputs leading to deep recursion

How to Handle:

An iterative solution is preferred to avoid potential stack overflow errors that a naive recursive solution might face with very long lists.

0/0 Capgemini questions completed

0/0 completed