Is Merge In Between Linked Lists easy or hard?

Merge In Between Linked Lists is categorized as a Medium problem. The main challenge is correctly identifying the nodes around indices a and b and reconnecting the pointers without breaking the list structure.

Merge In Between Linked Lists Python/Java solution

Most implementations iterate through list1 to find the boundary nodes, then connect list2 in place. The same logic works across Python, Java, C++, C#, and JavaScript because the solution relies on pointer references rather than language-specific libraries.

How to solve Merge In Between Linked Lists in O(n)?

Iterate through list1 to find the node just before index a and the node just after index b. Attach the head of list2 to the first boundary node, then find the tail of list2 and connect it to the node after b. This uses constant extra space and linear traversal.

What is the best approach for Merge In Between Linked Lists?

The best approach uses two pointers to locate the node before index a and the node after index b in list1. Connect the first node to the head of list2, then attach the tail of list2 to the remaining part of list1. This runs in O(n + m) time and O(1) space because it only rewires pointers.

Is Merge In Between Linked Lists asked at Google/Amazon/Meta?

Linked list pointer manipulation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants that involve cutting and reconnecting list segments are common because they test pointer reasoning and edge case handling.

What data structure is used in Merge In Between Linked Lists?

The problem uses singly linked lists. The main operations involve pointer traversal, locating specific indices, and reconnecting nodes without allocating additional data structures.

What is the time complexity of Merge In Between Linked Lists?

The optimal solution runs in O(n + m) time, where n is the length of list1 and m is the length of list2. You traverse list1 to locate the boundaries around indices a and b, and traverse list2 once to find its tail before reconnecting it.

Description Hints 3 Solution Video 6:22

1669. Merge In Between Linked Lists

Medium82.9% acceptance11 companies

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⁴

Asked at 11 companies

Sambanova Squarepoint Capital Oracle Arista Networks Tiktok NVIDIA PayPal

Google Amazon Microsoft Bloomberg

Topics

Linked List

Hints open one at a time

Hint 1

Check which edges need to be changed.

Hint 2

Let the next node of the (a-1)th node of list1 be the 0-th node in list 2.

Hint 3

Let the next node of the last node of list2 be the (b+1)-th node in list 1.

6:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
8        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[10,1,13,6,9,5]
3
4
[1000000,1000001,1000002]

Input

[0,1,2,3,4,5,6]
2
5
[1000000,1000001,1000002,1000003,1000004]

Your code is saved on this device.Solution