Problem statement

You are given two singly linked lists, list1 and list2, and two integers a <= b. Remove the nodes of list1 at positions a through b (0-indexed, inclusive) and put the whole of list2 in their place.

Return the head of the resulting list.

Example 1

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [100,101,102]
Output: [10,1,13,100,101,102,5]
Explanation: Positions 3 and 4 (values 6 and 9) are replaced by list2.

Example 2

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [90,91,92,93,94]
Output: [0,1,90,91,92,93,94,6]

Example 3

Input: list1 = [4,8,15], a = 1, b = 1, list2 = [16]
Output: [4,16,15]

Constraints

• 3 <= list1.length <= 10^4
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 10^4
• 0 <= Node.val <= 10^6

Hints for Merge In Between Linked Lists

1. Hint 1

   Only two places in list1 matter: the node just before position a and the node just after position b.

2. Hint 2

   Walk list1 once to find both (positions a - 1 and b + 1); the constraints guarantee they exist.

3. Hint 3

   Find the tail of list2, then link before.next = list2 and tail.next = after.

How to solve Merge In Between Linked Lists

Splicing a list in costs two link changes once the two boundary nodes are found: the node before the removed block points at list2, and list2's tail points at the node after the block.

Approach

1. Walk a - 1 steps from list1 to before.
2. Continue from before another b - a + 2 steps to after, the node at position b + 1.
3. Walk list2 to its last node tail.
4. Set before.next = list2, tail.next = after, and return list1.

Why it works

Positions a..b are exactly the nodes strictly between before and after; redirecting before to list2 and list2's tail to after removes them and inserts list2 in their place, leaving the rest of list1 linked as before. Since a >= 1, the head of list1 never changes.

Complexity

• Time — O(n + m)
• Space — O(1)

Pitfalls

• Off by one: before is at position a - 1 and after at b + 1.
• Forgetting to connect list2's tail cuts off the rest of list1.
• Find after before changing before.next, or the removed block is no longer reachable from before.

Reference solution

Python

from typing import Optional

def mergeInBetween(list1: Optional[ListNode], a: int, b: int, list2: Optional[ListNode]) -> Optional[ListNode]:
    before = list1
    for _ in range(a - 1):
        before = before.next
    after = before
    for _ in range(b - a + 2):
        after = after.next
    tail = list2
    while tail.next:
        tail = tail.next
    before.next = list2
    tail.next = after
    return list1

Java

public static ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
    ListNode before = list1;
    for (int i = 0; i < a - 1; i++) before = before.next;
    ListNode after = before;
    for (int j = 0; j < b - a + 2; j++) after = after.next;
    ListNode tail = list2;
    while (tail.next != null) tail = tail.next;
    before.next = list2;
    tail.next = after;
    return list1;
}

C++

ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
    ListNode* before = list1;
    for (int i = 0; i < a - 1; i++) before = before->next;
    ListNode* after = before;
    for (int j = 0; j < b - a + 2; j++) after = after->next;
    ListNode* tail = list2;
    while (tail->next) tail = tail->next;
    before->next = list2;
    tail->next = after;
    return list1;
}

JavaScript

var mergeInBetween = function(list1, a, b, list2) {
    var before = list1;
    for (var i = 0; i < a - 1; i++) before = before.next;
    var after = before;
    for (var j = 0; j < b - a + 2; j++) after = after.next;
    var tail = list2;
    while (tail.next !== null) tail = tail.next;
    before.next = list2;
    tail.next = after;
    return list1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Rotate a Linked List Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Swapping Nodes in a Linked List Medium