Jobs

Interviews

Discussions

Merge In Between Linked Lists

Medium

Asked by:

More companies

50 views

Topics:

Linked Lists

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the a^th node to the b^th node, and put list2 in their place.

The blue edges and nodes in the following figure indicate the result:

Build the result list and return its head.

Example 1:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Example 2:

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Constraints:

3 <= list1.length <= 10⁴
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10⁴

Try coding it in LeetCode

Merge In Between Linked Lists

Medium

Asked by:

50 views

Topics:

Linked Lists

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the a^th node to the b^th node, and put list2 in their place.

The blue edges and nodes in the following figure indicate the result:

Build the result list and return its head.

Example 1:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Example 2:

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Constraints:

3 <= list1.length <= 10⁴
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10⁴

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:

Can list1 or list2 ever be null or empty? If so, what should I return?
Are 'a' and 'b' zero-indexed or one-indexed?
Is it guaranteed that 'a' and 'b' are within the valid bounds of list1 (0 <= a <= b < length of list1) or should I handle out-of-bounds cases?
Should I modify the original list1 in-place, or return a new linked list?
What is the data type of the values stored in the linked lists, and is there a reasonable range for these values?

Brute Force Solution

Approach

The brute force method here is like trying every single possible way to splice one list into another. We test each insertion point to see if it works. It's all about checking every possibility until we find the right one.

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

First, go through the first list until you reach the starting point where you want to insert the second list.
Then, take the second list and connect its beginning to that point in the first list, temporarily combining them.
Next, find the ending point in the first list where the second list should stop being inserted.
Connect the end of the second list to that ending point in the first list, completing the insertion.
Check if this new combined list follows all the rules and requirements of the problem.
If it doesn't, try inserting the second list at a different location by going back to the first step.
Keep doing this, trying every possible starting and ending point in the first list to insert the second list, until you find an insertion that works.

Code Implementation

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

def merge_in_between_linked_lists(
        list1: ListNode,
        start_index: int,
        end_index: int,
        list2: ListNode) -> ListNode:

    # Find the node at the start index
    current_node_list1 = list1
    index = 0
    while index < start_index - 1:
        current_node_list1 = current_node_list1.next
        index += 1

    start_node = current_node_list1

    # Find the node after the end index
    current_node_list1 = list1
    index = 0
    while index < end_index:
        current_node_list1 = current_node_list1.next
        index += 1

    end_node = current_node_list1.next

    # Find the tail of list2
    current_node_list2 = list2
    while current_node_list2.next:
        current_node_list2 = current_node_list2.next

    # Connect the head of list2 to the start node
    start_node.next = list2

    # Connect the tail of list2 to the end node
    current_node_list2.next = end_node

    return list1

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible start positions in the first linked list (size n). For each start position, it iterates through all possible end positions after the start position in the first linked list (size n). For each combination of start and end positions, it checks if the merged list satisfies the problem constraints, potentially requiring traversal of the merged linked list (size n in the worst case). This results in roughly n * n * n operations, therefore the time complexity is O(n^3).

Space Complexity

O(1) – The brute force method described iterates through all possible insertion points without creating any new significant data structures. It modifies pointers of the existing linked lists in place. Therefore, it only requires a constant amount of extra space for variables to track the current insertion points, regardless of the size of the input lists. Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We are merging a linked list into another linked list within a specified range. The goal is to cut out a portion of the first list and insert the second list in its place. The efficient solution involves finding the nodes that define the start and end of the cut-out section in the first list and then carefully reconnecting the lists.

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

First, find the node in the first list where you want the merged list to begin. Imagine this as marking the start of where you want to make a change.
Next, find the node in the first list where you want the merged list to end. This marks the end of the section you want to replace.
Now, connect the node before the start of the section to the beginning of the second list. This is like attaching one chain to another.
If the second list is not empty, find the last node of the second list.
Finally, connect the end of the second list to the node after the end of the section you cut out of the first list. If the second list is empty, connect the node before the start of the section directly to the node after the end of the section.
By connecting these nodes correctly, you merge the second list into the first list, replacing the portion you wanted to change.

Code Implementation

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

def merge_in_between(list1: ListNode, start: int, end: int, list2: ListNode) -> ListNode:
    current_node = list1
    index = 0

    # Find the node before the start position.
    while index < start - 1:
        current_node = current_node.next
        index += 1

    node_before_start = current_node

    # Find the node at the end position.
    while index < end:
        current_node = current_node.next
        index += 1

    end_node = current_node.next

    # Connect the node before start to list2.
    node_before_start.next = list2

    # Find the last node of list2.
    if list2:
        current_list2_node = list2

        while current_list2_node.next:
            current_list2_node = current_list2_node.next

        # Connect the last node of list2 to the end node.
        current_list2_node.next = end_node

    else:
        # if list2 is empty, connect the node before start to end node
        node_before_start.next = end_node

    return list1

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves traversing the first linked list to find the nodes at indices a and b, taking O(a) and O(b) time, which is bounded by O(n) where n is the length of the first list. Finding the end of the second list (if it exists) takes O(m) time where m is the length of the second list. All connection operations are constant time. Since m is independent of n, and a and b are bounded by n, the overall time complexity is O(n + m), which simplifies to O(n) because we generally consider the length of the second list (m) to be less than or equal to the length of the first list (n).

Space Complexity

O(1) – The algorithm primarily involves traversing the linked lists and re-linking nodes. No auxiliary data structures like arrays, hash maps, or recursion are created that scale with the size of the input lists. We only use a few pointer variables to keep track of the current nodes during traversal and connection, and the number of these pointers is constant regardless of the list lengths. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
list1 is null	Return list2 if list1 is null, as list2 should be inserted in place of nothing.
list2 is null	Remove nodes from list1 from a to b, effectively deleting the sublist without insertion.
a == 0	list2 becomes the new head of the modified list1.
b is the last node of list1	Append the tail of list2 to the node before the ath node in list1.
a == b	Replace the ath node of list1 with list2.
a > b	Handle as an invalid input and either return null or throw an exception.
a or b are out of bounds (e.g., a < 0 or b >= length of list1)	Handle as an invalid input, either returning null or throwing an exception.
list1 and list2 are very long	Ensure the solution uses iterative approach to avoid potential stack overflow issues.

list1 is null

How to Handle:

Return list2 if list1 is null, as list2 should be inserted in place of nothing.

list2 is null

How to Handle:

Remove nodes from list1 from a to b, effectively deleting the sublist without insertion.

a == 0

How to Handle:

list2 becomes the new head of the modified list1.

b is the last node of list1

How to Handle:

Append the tail of list2 to the node before the ath node in list1.

a == b

How to Handle:

Replace the ath node of list1 with list2.

a > b

How to Handle:

Handle as an invalid input and either return null or throw an exception.

a or b are out of bounds (e.g., a < 0 or b >= length of list1)

How to Handle:

Handle as an invalid input, either returning null or throwing an exception.

list1 and list2 are very long

How to Handle:

Ensure the solution uses iterative approach to avoid potential stack 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:

Can list1 or list2 ever be null or empty? If so, what should I return?
Are 'a' and 'b' zero-indexed or one-indexed?
Is it guaranteed that 'a' and 'b' are within the valid bounds of list1 (0 <= a <= b < length of list1) or should I handle out-of-bounds cases?
Should I modify the original list1 in-place, or return a new linked list?
What is the data type of the values stored in the linked lists, and is there a reasonable range for these values?

Brute Force Solution

Approach

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

First, go through the first list until you reach the starting point where you want to insert the second list.
Then, take the second list and connect its beginning to that point in the first list, temporarily combining them.
Next, find the ending point in the first list where the second list should stop being inserted.
Connect the end of the second list to that ending point in the first list, completing the insertion.
Check if this new combined list follows all the rules and requirements of the problem.
If it doesn't, try inserting the second list at a different location by going back to the first step.
Keep doing this, trying every possible starting and ending point in the first list to insert the second list, until you find an insertion that works.

Code Implementation

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

def merge_in_between_linked_lists(
        list1: ListNode,
        start_index: int,
        end_index: int,
        list2: ListNode) -> ListNode:

    # Find the node at the start index
    current_node_list1 = list1
    index = 0
    while index < start_index - 1:
        current_node_list1 = current_node_list1.next
        index += 1

    start_node = current_node_list1

    # Find the node after the end index
    current_node_list1 = list1
    index = 0
    while index < end_index:
        current_node_list1 = current_node_list1.next
        index += 1

    end_node = current_node_list1.next

    # Find the tail of list2
    current_node_list2 = list2
    while current_node_list2.next:
        current_node_list2 = current_node_list2.next

    # Connect the head of list2 to the start node
    start_node.next = list2

    # Connect the tail of list2 to the end node
    current_node_list2.next = end_node

    return list1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the node in the first list where you want the merged list to begin. Imagine this as marking the start of where you want to make a change.
Next, find the node in the first list where you want the merged list to end. This marks the end of the section you want to replace.
Now, connect the node before the start of the section to the beginning of the second list. This is like attaching one chain to another.
If the second list is not empty, find the last node of the second list.
Finally, connect the end of the second list to the node after the end of the section you cut out of the first list. If the second list is empty, connect the node before the start of the section directly to the node after the end of the section.
By connecting these nodes correctly, you merge the second list into the first list, replacing the portion you wanted to change.

Code Implementation

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

def merge_in_between(list1: ListNode, start: int, end: int, list2: ListNode) -> ListNode:
    current_node = list1
    index = 0

    # Find the node before the start position.
    while index < start - 1:
        current_node = current_node.next
        index += 1

    node_before_start = current_node

    # Find the node at the end position.
    while index < end:
        current_node = current_node.next
        index += 1

    end_node = current_node.next

    # Connect the node before start to list2.
    node_before_start.next = list2

    # Find the last node of list2.
    if list2:
        current_list2_node = list2

        while current_list2_node.next:
            current_list2_node = current_list2_node.next

        # Connect the last node of list2 to the end node.
        current_list2_node.next = end_node

    else:
        # if list2 is empty, connect the node before start to end node
        node_before_start.next = end_node

    return list1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
list1 is null	Return list2 if list1 is null, as list2 should be inserted in place of nothing.
list2 is null	Remove nodes from list1 from a to b, effectively deleting the sublist without insertion.
a == 0	list2 becomes the new head of the modified list1.
b is the last node of list1	Append the tail of list2 to the node before the ath node in list1.
a == b	Replace the ath node of list1 with list2.
a > b	Handle as an invalid input and either return null or throw an exception.
a or b are out of bounds (e.g., a < 0 or b >= length of list1)	Handle as an invalid input, either returning null or throwing an exception.
list1 and list2 are very long	Ensure the solution uses iterative approach to avoid potential stack overflow issues.

list1 is null

How to Handle:

Return list2 if list1 is null, as list2 should be inserted in place of nothing.

list2 is null

How to Handle:

Remove nodes from list1 from a to b, effectively deleting the sublist without insertion.

a == 0

How to Handle:

list2 becomes the new head of the modified list1.

b is the last node of list1

How to Handle:

Append the tail of list2 to the node before the ath node in list1.

a == b

How to Handle:

Replace the ath node of list1 with list2.

a > b

How to Handle:

Handle as an invalid input and either return null or throw an exception.

a or b are out of bounds (e.g., a < 0 or b >= length of list1)

How to Handle:

Handle as an invalid input, either returning null or throwing an exception.

list1 and list2 are very long

How to Handle:

Ensure the solution uses iterative approach to avoid potential stack overflow issues.