Jobs

Interviews

Discussions

Merge Two Sorted Lists

Easy

Amazon

4 views

Topics:

Linked ListsTwo Pointers

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:

list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

Example 2:

list1 = [], list2 = []

Output: []

Example 3:

list1 = [], list2 = [0]

Output: [0]

Can you implement a function that merges two sorted linked lists into a single sorted linked list? Consider edge cases such as empty lists. What is the time and space complexity of your solution?

Merge Two Sorted Lists

Easy

Amazon

4 views

Topics:

Linked ListsTwo Pointers

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:

list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

Example 2:

list1 = [], list2 = []

Output: []

Example 3:

list1 = [], list2 = [0]

Output: [0]

Can you implement a function that merges two sorted linked lists into a single sorted linked list? Consider edge cases such as empty lists. What is the time and space complexity of your solution?

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 is the range of values that the nodes in the linked lists can hold?
Can either list1 or list2 be null or empty?
If both lists are empty, should I return null?
Can the same value appear multiple times within a single linked list?
Should the new merged list be a new list, or can I modify the existing list1 and list2 lists in place to create the merged list?

Brute Force Solution

Approach

The brute force method for merging two sorted lists involves exhaustively comparing elements from both lists and building a completely new merged list. We essentially explore every possible combination of elements to find the correct sorted order. This is like manually sorting a shuffled deck of cards by constantly comparing pairs and rearranging them.

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

Start by creating a brand new, empty list that will hold the merged result.
Look at the very first element in both lists. Compare them to each other.
Take the smaller of the two elements and put it at the end of the new, merged list.
Remove the element you just added from its original list.
Repeat the process of comparing the first elements of the remaining parts of both lists, adding the smaller one to the merged list, and removing it from its original list.
Continue this process until one of the lists is completely empty.
Once one list is empty, take all the remaining elements from the other list and simply add them to the end of the new, merged list. Since the original lists were already sorted, all the remaining elements will be larger than anything already in the merged list and will maintain the sorted order.

Code Implementation

def merge_two_sorted_lists_brute_force(list1, list2):
    merged_list = []

    while list1 and list2:
        # Compare the first elements of both lists.
        if list1[0] <= list2[0]:
            merged_list.append(list1[0])
            list1.pop(0)

        else:
            merged_list.append(list2[0])
            list2.pop(0)

    # If list1 has remaining elements, add them.
    if list1:
        # List1 still contains elements
        merged_list.extend(list1)

    # If list2 has remaining elements, add them.
    if list2:
        # List2 still contains elements
        merged_list.extend(list2)

    return merged_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through both input lists, comparing elements and adding them to the merged list. In the worst case, where the elements are interleaved, it will need to consider each element from both lists exactly once. This results in a single pass through a combined total of 'n' elements, where 'n' represents the sum of the lengths of the two input lists. Therefore, the time complexity is directly proportional to the total number of elements, making it O(n).

Space Complexity

O(N) – The algorithm creates a new list to store the merged result. The size of this merged list will be at most the sum of the lengths of the two input lists. Therefore, if N represents the total number of elements in the two input lists, the algorithm uses an auxiliary array of size N. Hence, the space complexity is O(N).

Optimal Solution

Approach

We're given two sorted lists and need to combine them into one sorted list. The key idea is to avoid unnecessary comparisons by always picking the smallest element from the heads of the two lists to build our final sorted list. This ensures we build the merged list in the correct order efficiently.

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

Imagine you have two lines of people sorted by height, and you need to merge them into one sorted line.
Look at the first person in each line. Pick the shorter one to be the first person in your merged line.
Move to the next person in the line you just picked from.
Again, look at the first person in each (modified) line. Pick the shorter one to be the next person in your merged line.
Keep repeating this process until one of the lines runs out of people.
Once one line is empty, simply add all the remaining people from the other line to the end of the merged line, since they are already sorted.

Code Implementation

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

def mergeTwoLists(list1, list2):
    # Create a dummy node to simplify the head insertion.
    dummy_node = ListNode()
    tail_node = dummy_node

    while list1 and list2:
        # Pick the smaller value node and advance.
        if list1.val <= list2.val:
            tail_node.next = list1
            list1 = list1.next
        else:
            tail_node.next = list2
            list2 = list2.next
        tail_node = tail_node.next

    # Attach the remaining elements of the other list
    if list1:
        tail_node.next = list1

    if list2:
        tail_node.next = list2

    return dummy_node.next

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by how many times we need to examine elements from the two input lists. In the worst case, we iterate through all the elements in both lists once. Let n be the total number of elements in both lists (the sum of the lengths of the two lists). We perform a constant-time comparison for each element until one list is exhausted, and then append the remaining elements of the other list. Therefore, the algorithm has a linear time complexity, O(n).

Space Complexity

O(1) – The algorithm described in the plain English explanation does not explicitly mention creating any new data structures that grow with the input size. The process involves comparing elements from the heads of the input lists and iteratively building the merged list, implying in-place manipulation. Therefore, it uses a constant amount of auxiliary space for variables like pointers or iterators, irrespective of the total number of elements in the input lists (N).

Edge Cases

Case	How to Handle
Both lists are null	Return null immediately as there is nothing to merge.
One list is null, the other is not	Return the non-null list as the merged list.
One or both lists contain only one node	The iterative merging process should correctly handle lists with only one node by simply appending it at the correct position.
Both lists contain the same single value	The iterative process correctly appends both nodes in sorted order.
Lists contain many duplicate values (e.g., many 1's, many 2's)	The iterative approach handles duplicate values without issue, as it compares node values directly.
All values in list1 are smaller than all values in list2	The iterative comparison correctly appends all list1 nodes before appending list2 nodes.
List1 is much longer than list2 (or vice versa)	The while loop condition accounts for only one of the list reaching the end, appends the other longer list.
List elements contain negative numbers, zeros, and large positive numbers	The iterative comparison should work regardless of the value, as long as they are comparable.

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 is the range of values that the nodes in the linked lists can hold?
Can either list1 or list2 be null or empty?
If both lists are empty, should I return null?
Can the same value appear multiple times within a single linked list?
Should the new merged list be a new list, or can I modify the existing list1 and list2 lists in place to create the merged list?

Brute Force Solution

Approach

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

Start by creating a brand new, empty list that will hold the merged result.
Look at the very first element in both lists. Compare them to each other.
Take the smaller of the two elements and put it at the end of the new, merged list.
Remove the element you just added from its original list.
Repeat the process of comparing the first elements of the remaining parts of both lists, adding the smaller one to the merged list, and removing it from its original list.
Continue this process until one of the lists is completely empty.
Once one list is empty, take all the remaining elements from the other list and simply add them to the end of the new, merged list. Since the original lists were already sorted, all the remaining elements will be larger than anything already in the merged list and will maintain the sorted order.

Code Implementation

def merge_two_sorted_lists_brute_force(list1, list2):
    merged_list = []

    while list1 and list2:
        # Compare the first elements of both lists.
        if list1[0] <= list2[0]:
            merged_list.append(list1[0])
            list1.pop(0)

        else:
            merged_list.append(list2[0])
            list2.pop(0)

    # If list1 has remaining elements, add them.
    if list1:
        # List1 still contains elements
        merged_list.extend(list1)

    # If list2 has remaining elements, add them.
    if list2:
        # List2 still contains elements
        merged_list.extend(list2)

    return merged_list

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 sorted by height, and you need to merge them into one sorted line.
Look at the first person in each line. Pick the shorter one to be the first person in your merged line.
Move to the next person in the line you just picked from.
Again, look at the first person in each (modified) line. Pick the shorter one to be the next person in your merged line.
Keep repeating this process until one of the lines runs out of people.
Once one line is empty, simply add all the remaining people from the other line to the end of the merged line, since they are already sorted.

Code Implementation

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

def mergeTwoLists(list1, list2):
    # Create a dummy node to simplify the head insertion.
    dummy_node = ListNode()
    tail_node = dummy_node

    while list1 and list2:
        # Pick the smaller value node and advance.
        if list1.val <= list2.val:
            tail_node.next = list1
            list1 = list1.next
        else:
            tail_node.next = list2
            list2 = list2.next
        tail_node = tail_node.next

    # Attach the remaining elements of the other list
    if list1:
        tail_node.next = list1

    if list2:
        tail_node.next = list2

    return dummy_node.next

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both lists are null	Return null immediately as there is nothing to merge.
One list is null, the other is not	Return the non-null list as the merged list.
One or both lists contain only one node	The iterative merging process should correctly handle lists with only one node by simply appending it at the correct position.
Both lists contain the same single value	The iterative process correctly appends both nodes in sorted order.
Lists contain many duplicate values (e.g., many 1's, many 2's)	The iterative approach handles duplicate values without issue, as it compares node values directly.
All values in list1 are smaller than all values in list2	The iterative comparison correctly appends all list1 nodes before appending list2 nodes.
List1 is much longer than list2 (or vice versa)	The while loop condition accounts for only one of the list reaching the end, appends the other longer list.
List elements contain negative numbers, zeros, and large positive numbers	The iterative comparison should work regardless of the value, as long as they are comparable.