Jobs

Interviews

Discussions

Merge Two Sorted Lists

Easy

Rippling

0 views

Topics:

Linked Lists

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.

Merge Two Sorted Lists

Easy

Rippling

0 views

Topics:

Linked Lists

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.

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:

Can the input lists be empty or null?
What is the range of values within the nodes of the linked lists?
Should the merged list be a new list, or can I modify the existing lists?
Are duplicate values allowed within the input lists, and should duplicates be preserved in the merged list?
Is it guaranteed that both input lists are actually sorted in non-decreasing order?

Brute Force Solution

Approach

The brute force way to combine two sorted lists is to simply create a new, third list and put all elements from both lists into it. After that, we sort the combined list to achieve the final merged, sorted order. It is like mixing two decks of sorted playing cards, and then re-sorting the whole deck.

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

First, create a brand-new, empty list to hold all the items.
Next, take all the items from the first sorted list and put them into this new list, one by one.
Then, take all the items from the second sorted list and also put them into the same new list, one by one.
Now that our new list has all the items from both original lists, the last step is to sort the whole list so that the items are in the correct order from smallest to largest.

Code Implementation

def merge_two_sorted_lists_brute_force(list1, list2): 
    # Create a new list to hold all elements
    merged_list = []

    # Add all elements from the first list
    for element_from_list1 in list1:
        merged_list.append(element_from_list1)

    # Add all elements from the second list
    for element_from_list2 in list2:
        merged_list.append(element_from_list2)

    # Sort the merged list to ensure correct order
    merged_list.sort()

    return merged_list

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The described algorithm involves creating a new list containing all elements from the two input lists. If we denote the size of the first list as n and the size of the second list as m, creating the combined list takes O(n+m) time. The dominant operation is sorting this combined list of size (n+m). A typical efficient sorting algorithm, like merge sort or quicksort, has a time complexity of O((n+m) log (n+m)). If we let k = n+m, this simplifies to O(k log k), where k is the total number of elements. Because the sorting dominates, the overall time complexity is O(n log n) assuming the two input lists are of similar sizes (and where 'n' represents the combined size), or more accurately, O((n+m)log(n+m)).

Space Complexity

O(N) – The provided brute force solution creates a new list to hold all elements from the two input lists. The size of this new list grows linearly with the total number of elements in the input lists. If we denote the total number of elements in both input lists as N, then the new list will have a size of N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The clever way to merge two sorted lists is to build a new sorted list piece by piece, always picking the smallest element available. Instead of combining the lists and then sorting, we directly create a sorted result. This saves time by avoiding a full sort at the end.

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

Imagine you have two lines of students, both already sorted by height, shortest to tallest.
To create one combined sorted line, peek at the front of each line and choose the shortest student.
Add that shortest student to the end of your new combined line.
Move the student you picked from their original line to the back of your new combined line.
Repeat the process of peeking and picking the shortest, until one of the original lines is empty.
Once one line is empty, just add the rest of the students from the other line to the end of your combined line, since they're already in the correct order.
The combined line will now contain all students, still sorted from shortest to tallest.

Code Implementation

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

def mergeTwoLists(list1, list2):
    # Handle the case where either list is empty.
    if not list1:
        return list2
    if not list2:
        return list1

    # Initialize the head of the merged list.
    if list1.val <= list2.val:
        merged_head = list1
        list1 = list1.next
    else:
        merged_head = list2
        list2 = list2.next
    
    current_node = merged_head

    # Iterate while both lists have elements.
    while list1 and list2:
        # Choose the smaller value from the two lists.
        if list1.val <= list2.val:
            current_node.next = list1
            list1 = list1.next
        else:
            current_node.next = list2
            list2 = list2.next
        current_node = current_node.next

    # Append the remaining elements from list1, if any.
    if list1:
        current_node.next = list1

    # Append the remaining elements from list2, if any.
    if list2:
        current_node.next = list2

    return merged_head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through both input lists, l1 and l2, at most once. The number of steps is proportional to the total number of nodes in both lists. If 'n' represents the total number of nodes across both lists (n = length(l1) + length(l2)), then the algorithm performs a constant amount of work (comparison and node linking) for each of these 'n' nodes. Therefore, the time complexity is directly proportional to 'n', resulting in O(n).

Space Complexity

O(1) – The iterative merging approach described in the plain English explanation builds the merged list in-place, by modifying the `next` pointers of the existing list nodes. There are no auxiliary data structures like temporary lists or hash maps used to store a copy of all elements, intermediate results, or visited nodes. The algorithm only requires a few pointer variables to keep track of the current nodes in each list. Therefore, the space used remains constant regardless of the size of the input lists, making the auxiliary space complexity O(1).

Edge Cases

Case	How to Handle
Both input lists are null	Return null since there's nothing to merge.
One list is null, the other is not	Return the non-null list directly as it is already sorted.
Both lists are empty (have no nodes)	Return null since the result should be an empty list.
One list is empty, the other has one or more nodes	Return the non-empty list.
Lists contain duplicate values	The standard merging logic handles duplicates correctly, preserving their order.
Lists contain negative values, zeros, and positive values	The comparison based merging logic works correctly regardless of the sign of the values.
One list has significantly fewer nodes than the other	The algorithm will iterate through the shorter list and then append the remainder of the longer list.
Lists are identical (contain the same values in the same order)	The merging process will interleave the identical values, maintaining the sorted order.

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:

Can the input lists be empty or null?
What is the range of values within the nodes of the linked lists?
Should the merged list be a new list, or can I modify the existing lists?
Are duplicate values allowed within the input lists, and should duplicates be preserved in the merged list?
Is it guaranteed that both input lists are actually sorted in non-decreasing order?

Brute Force Solution

Approach

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

First, create a brand-new, empty list to hold all the items.
Next, take all the items from the first sorted list and put them into this new list, one by one.
Then, take all the items from the second sorted list and also put them into the same new list, one by one.
Now that our new list has all the items from both original lists, the last step is to sort the whole list so that the items are in the correct order from smallest to largest.

Code Implementation

def merge_two_sorted_lists_brute_force(list1, list2): 
    # Create a new list to hold all elements
    merged_list = []

    # Add all elements from the first list
    for element_from_list1 in list1:
        merged_list.append(element_from_list1)

    # Add all elements from the second list
    for element_from_list2 in list2:
        merged_list.append(element_from_list2)

    # Sort the merged list to ensure correct order
    merged_list.sort()

    return merged_list

Try it yourself on LeetCode

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 students, both already sorted by height, shortest to tallest.
To create one combined sorted line, peek at the front of each line and choose the shortest student.
Add that shortest student to the end of your new combined line.
Move the student you picked from their original line to the back of your new combined line.
Repeat the process of peeking and picking the shortest, until one of the original lines is empty.
Once one line is empty, just add the rest of the students from the other line to the end of your combined line, since they're already in the correct order.
The combined line will now contain all students, still sorted from shortest to tallest.

Code Implementation

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

def mergeTwoLists(list1, list2):
    # Handle the case where either list is empty.
    if not list1:
        return list2
    if not list2:
        return list1

    # Initialize the head of the merged list.
    if list1.val <= list2.val:
        merged_head = list1
        list1 = list1.next
    else:
        merged_head = list2
        list2 = list2.next
    
    current_node = merged_head

    # Iterate while both lists have elements.
    while list1 and list2:
        # Choose the smaller value from the two lists.
        if list1.val <= list2.val:
            current_node.next = list1
            list1 = list1.next
        else:
            current_node.next = list2
            list2 = list2.next
        current_node = current_node.next

    # Append the remaining elements from list1, if any.
    if list1:
        current_node.next = list1

    # Append the remaining elements from list2, if any.
    if list2:
        current_node.next = list2

    return merged_head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input lists are null	Return null since there's nothing to merge.
One list is null, the other is not	Return the non-null list directly as it is already sorted.
Both lists are empty (have no nodes)	Return null since the result should be an empty list.
One list is empty, the other has one or more nodes	Return the non-empty list.
Lists contain duplicate values	The standard merging logic handles duplicates correctly, preserving their order.
Lists contain negative values, zeros, and positive values	The comparison based merging logic works correctly regardless of the sign of the values.
One list has significantly fewer nodes than the other	The algorithm will iterate through the shorter list and then append the remainder of the longer list.
Lists are identical (contain the same values in the same order)	The merging process will interleave the identical values, maintaining the sorted order.