Jobs

Interviews

Discussions

Merge Two Sorted Lists

#17 Most AskedEasy

Merge Two Sorted Lists #17 Most Asked

Easy

Arista Networks

8 views

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

#17 Most AskedEasy

Merge Two Sorted Lists #17 Most Asked

Easy

Arista Networks

8 views

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?
Are the values within the linked list nodes guaranteed to be integers, or could they be other data types like floats or characters?
How should duplicates be handled? If a value exists in both lists, should the merged list preserve all instances from both?
What are the constraints on the number of nodes in each list and the range of values within the nodes?
Is it acceptable to modify the input lists by rearranging their nodes, or should I create an entirely new list?

Brute Force Solution

Approach

The brute force strategy involves combining all the items from both lists into one big, unsorted collection first. Then, it sorts this combined collection from scratch to get the final merged and sorted list.

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

First, create a new, empty collection.
Go through the first sorted list and add every single item from it into this new collection.
Next, go through the second sorted list and also add all of its items to the same new collection.
At this point, you have one large collection with all the items, but they are not in order.
Now, sort this entire large collection from the smallest item to the largest item.
Finally, present this newly sorted collection as the final result.

Code Implementation

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

def merge_two_lists_brute_force(first_list_head, second_list_head):
    all_values = []
    current_node = first_list_head

    # First, collect all values from the first list into a single collection.
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    current_node = second_list_head

    # Next, collect all values from the second list into the same collection.
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    # Sort the combined collection of values to establish the final merged order.
    all_values.sort()

    dummy_head = ListNode()
    current_new_node = dummy_head

    # Finally, construct a new linked list from the sorted values.
    for value in all_values:
        current_new_node.next = ListNode(value)
        current_new_node = current_new_node.next

    return dummy_head.next

Big(O) Analysis

Time Complexity

O((n + m) log (n + m)) – The complexity is driven by the sorting step. Let n be the number of items in the first list and m be the number of items in the second. First, we iterate through both lists to create a combined collection of size (n + m), which takes O(n + m) time. The dominant operation is sorting this combined collection. A standard, efficient sorting algorithm has a time complexity of O(k log k), where k is the number of items. In this case, k equals (n + m), leading to a total time complexity of O((n + m) log (n + m)).

Space Complexity

O(N) – The brute force strategy requires creating a new collection to hold all the elements from both input lists. If the first list has M elements and the second has L elements, this new collection will store M + L items, where N represents the total number of elements (M + L). The space required for this collection grows linearly with the total number of elements in the input lists, as it must hold a copy of every single item before sorting.

Optimal Solution

Approach

The most efficient way to solve this is by building the new sorted list one piece at a time. We repeatedly look at the smallest available items from both original lists and pick the smaller of the two to add to our new list, advancing only the list we picked from.

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

Imagine you have two lines of people, each already sorted by height from shortest to tallest.
First, create a starting point for a new, third line that will be our final merged result.
Look at the first person in each of the two original lines.
Compare them and ask the shorter of the two to step into your new line.
Whichever line that person came from, you now look at the next person in that same line. The other line's front person stays put.
Repeat the process: compare the two people now at the front of each original line, pick the shorter one, and add them to the end of your new line.
Continue this comparison until one of the original lines is completely empty.
Once one line is empty, you know everyone left in the other line is taller than anyone you've picked so far. So, just take that entire remaining line and attach it to the end of your new line.
The new line you've built is now a single, perfectly sorted combination of the original two.

Code Implementation

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

def mergeTwoLists(list_node1, list_node2):
    # Create a starting point for the new merged list, which helps manage the head of the new list.
    dummy_head = ListNode()

    current_merged_list_pointer = dummy_head

    while list_node1 and list_node2:
        # Compare nodes from both lists to decide which one to add next to maintain sorted order.
        if list_node1.val < list_node2.val:
            current_merged_list_pointer.next = list_node1
            list_node1 = list_node1.next
        else:
            current_merged_list_pointer.next = list_node2
            list_node2 = list_node2.next
        current_merged_list_pointer = current_merged_list_pointer.next

    # If one list is exhausted, the other must contain all remaining (and larger) elements.
    if list_node1:
        current_merged_list_pointer.next = list_node1
    elif list_node2:
        current_merged_list_pointer.next = list_node2

    # The merged list starts right after the dummy node we created.
    return dummy_head.next

Big(O) Analysis

Time Complexity

O(n + m) – Let n be the number of nodes in the first list and m be the number of nodes in the second. The algorithm iterates through both lists exactly once, comparing one node from each list at every step. Each comparison and node addition is a constant time operation, and we perform one such operation for every single node across both lists. Therefore, the total number of operations is directly proportional to the total number of nodes, which is n + m, simplifying to O(n + m).

Space Complexity

O(1) – The algorithm constructs the new sorted list by rearranging the existing nodes from the two input lists. The only extra memory used is for a few pointers to keep track of the current nodes being compared and the head of the new list. This memory usage is constant and does not depend on the number of nodes in the input lists, which we can denote as N (the total number of elements).

Edge Cases

Case	How to Handle
One or both input lists are null or empty	The algorithm should return the non-null list, or null if both are empty.
One list is exhausted while the other still has elements	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 smaller node becomes the head, and its next pointer is set to the larger node.
Lists contain duplicate values across or within them	The relative order of duplicate values is preserved by the stable merging logic.
Lists contain negative numbers and zeros	The standard comparison logic correctly handles negative numbers, zeros, and positive numbers.
One list is significantly longer than the other	The solution efficiently appends the long remaining tail after the shorter list is fully merged.
All elements in one list are smaller than all elements in the other	The algorithm will append the second list entirely to the end of the first list.
Lists have nodes with extreme values (e.g., Integer.MIN_VALUE, Integer.MAX_VALUE)	Standard integer comparisons will handle these boundary values correctly without overflow issues.

One or both input lists are null or empty

How to Handle:

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

One list is exhausted while the other still has elements

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 smaller node becomes the head, and its next pointer is set to the larger node.

Lists contain duplicate values across or within them

How to Handle:

The relative order of duplicate values is preserved by the stable merging logic.

Lists contain negative numbers and zeros

How to Handle:

The standard comparison logic correctly handles negative numbers, zeros, and positive numbers.

One list is significantly longer than the other

How to Handle:

The solution efficiently appends the long remaining tail after the shorter list is fully merged.

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

How to Handle:

The algorithm will append the second list entirely to the end of the first list.

Lists have nodes with extreme values (e.g., Integer.MIN_VALUE, Integer.MAX_VALUE)

How to Handle:

Standard integer comparisons will handle these boundary values correctly without overflow issues.

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?
Are the values within the linked list nodes guaranteed to be integers, or could they be other data types like floats or characters?
How should duplicates be handled? If a value exists in both lists, should the merged list preserve all instances from both?
What are the constraints on the number of nodes in each list and the range of values within the nodes?
Is it acceptable to modify the input lists by rearranging their nodes, or should I create an entirely new list?

Brute Force Solution

Approach

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

First, create a new, empty collection.
Go through the first sorted list and add every single item from it into this new collection.
Next, go through the second sorted list and also add all of its items to the same new collection.
At this point, you have one large collection with all the items, but they are not in order.
Now, sort this entire large collection from the smallest item to the largest item.
Finally, present this newly sorted collection as the final result.

Code Implementation

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

def merge_two_lists_brute_force(first_list_head, second_list_head):
    all_values = []
    current_node = first_list_head

    # First, collect all values from the first list into a single collection.
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    current_node = second_list_head

    # Next, collect all values from the second list into the same collection.
    while current_node is not None:
        all_values.append(current_node.val)
        current_node = current_node.next

    # Sort the combined collection of values to establish the final merged order.
    all_values.sort()

    dummy_head = ListNode()
    current_new_node = dummy_head

    # Finally, construct a new linked list from the sorted values.
    for value in all_values:
        current_new_node.next = ListNode(value)
        current_new_node = current_new_node.next

    return dummy_head.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 already sorted by height from shortest to tallest.
First, create a starting point for a new, third line that will be our final merged result.
Look at the first person in each of the two original lines.
Compare them and ask the shorter of the two to step into your new line.
Whichever line that person came from, you now look at the next person in that same line. The other line's front person stays put.
Repeat the process: compare the two people now at the front of each original line, pick the shorter one, and add them to the end of your new line.
Continue this comparison until one of the original lines is completely empty.
Once one line is empty, you know everyone left in the other line is taller than anyone you've picked so far. So, just take that entire remaining line and attach it to the end of your new line.
The new line you've built is now a single, perfectly sorted combination of the original two.

Code Implementation

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

def mergeTwoLists(list_node1, list_node2):
    # Create a starting point for the new merged list, which helps manage the head of the new list.
    dummy_head = ListNode()

    current_merged_list_pointer = dummy_head

    while list_node1 and list_node2:
        # Compare nodes from both lists to decide which one to add next to maintain sorted order.
        if list_node1.val < list_node2.val:
            current_merged_list_pointer.next = list_node1
            list_node1 = list_node1.next
        else:
            current_merged_list_pointer.next = list_node2
            list_node2 = list_node2.next
        current_merged_list_pointer = current_merged_list_pointer.next

    # If one list is exhausted, the other must contain all remaining (and larger) elements.
    if list_node1:
        current_merged_list_pointer.next = list_node1
    elif list_node2:
        current_merged_list_pointer.next = list_node2

    # The merged list starts right after the dummy node we created.
    return dummy_head.next

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
One or both input lists are null or empty	The algorithm should return the non-null list, or null if both are empty.
One list is exhausted while the other still has elements	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 smaller node becomes the head, and its next pointer is set to the larger node.
Lists contain duplicate values across or within them	The relative order of duplicate values is preserved by the stable merging logic.
Lists contain negative numbers and zeros	The standard comparison logic correctly handles negative numbers, zeros, and positive numbers.
One list is significantly longer than the other	The solution efficiently appends the long remaining tail after the shorter list is fully merged.
All elements in one list are smaller than all elements in the other	The algorithm will append the second list entirely to the end of the first list.
Lists have nodes with extreme values (e.g., Integer.MIN_VALUE, Integer.MAX_VALUE)	Standard integer comparisons will handle these boundary values correctly without overflow issues.

One or both input lists are null or empty

How to Handle:

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

One list is exhausted while the other still has elements

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 smaller node becomes the head, and its next pointer is set to the larger node.

Lists contain duplicate values across or within them

How to Handle:

The relative order of duplicate values is preserved by the stable merging logic.

Lists contain negative numbers and zeros

How to Handle:

The standard comparison logic correctly handles negative numbers, zeros, and positive numbers.

One list is significantly longer than the other

How to Handle:

The solution efficiently appends the long remaining tail after the shorter list is fully merged.

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

How to Handle:

The algorithm will append the second list entirely to the end of the first list.

Lists have nodes with extreme values (e.g., Integer.MIN_VALUE, Integer.MAX_VALUE)

How to Handle:

Standard integer comparisons will handle these boundary values correctly without overflow issues.

0/42 Arista Networks questions completed

0/42 completed