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 (0-indexed), and put list2 in their place.

Examples

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]

list1:  10 → 1 → 13 → [6 → 9] → 5
                        ↑ remove ↑
list2:  1000000 → 1000001 → 1000002

Result: 10 → 1 → 13 → 1000000 → 1000001 → 1000002 → 5

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]

Constraints

  • 3 <= list1.length <= 10^4
  • 1 <= a <= b < list1.length - 1
  • 1 <= list2.length <= 10^4

The constraints guarantee a >= 1 and b < n - 1, so there is always at least one node before a and one node after b.

Thinking Process

What Do We Need?

We’re splicing list2 into list1 by removing positions a..b. That means three pointer rewirings:

prevA → list2_head → ... → list2_tail → afterB

We need:

  1. prevA – the node at index a - 1 (just before the removed segment)
  2. afterB – the node at index b + 1 (just after the removed segment)
  3. tail2 – the last node of list2

Why No Dummy Node Needed?

Since a >= 1, the head of list1 is never removed, so we don’t need a dummy node to protect the head.

Walk-through

list1: 10 → 1 → 13 → 6 → 9 → 5     a=3, b=4
index:  0   1    2   3   4   5

Step 1: Walk to index a-1 = 2
  prevA = node(13)

Step 2: From prevA, walk (b - a + 1) more steps to reach node at index b
  then afterB = that node's next
  afterB = node(5)

Step 3: Find tail of list2
  list2: 1000000 → 1000001 → 1000002
  tail2 = node(1000002)

Step 4: Rewire
  prevA.next = list2         →  13 → 1000000
  tail2.next = afterB        →  1000002 → 5

Result: 10 → 1 → 13 → 1000000 → 1000001 → 1000002 → 5  ✓
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

from typing import Optional


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeInBetween(
        self, list1: "ListNode", a: int, b: int, list2: "ListNode"
    ) -> "ListNode":
        dummy = ListNode(0, list1)
        prevA = dummy

        # Find node before index a.
        for _ in range(a):
            prevA = prevA.next

        # Move to node at index b, then step once more to index b+1.
        afterB = prevA
        for _ in range(b - a + 1):
            afterB = afterB.next
        afterB = afterB.next

        # Attach list2 at cut position.
        prevA.next = list2

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

        # Connect tail of list2 to remainder of list1.
        tail.next = afterB

        return dummy.next

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: ### What Do We Need?

How the code works:

  1. prevA – the node at index a - 1 (just before the removed segment)
  2. afterB – the node at index b + 1 (just after the removed segment)
  3. tail2 – the last node of list2

Walkthrough — input list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002], expected output [10,1,13,1000000,1000001,1000002,5]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

Time: O(n + m) – traverse list1 up to index b, then traverse all of list2 · Space: O(1) – only pointer variables## Key Details

Without Dummy (Slightly Simpler)

Since the constraints guarantee a >= 1, we can skip the dummy:

class Solution:
    def mergeInBetween(
        self, list1: "ListNode", a: int, b: int, list2: "ListNode"
    ) -> "ListNode":
        prevA = list1
        for _ in range(a - 1):
            prevA = prevA.next

        afterB = prevA
        for _ in range(b - a + 1):
            afterB = afterB.next

        prevA.next = list2

        tail = list2
        while tail.next:
            tail = tail.next
        tail.next = afterB

        return list1

Common Mistakes

  • Off-by-one on prevA: Walking a steps from head lands on index a, but we need index a - 1. Use a dummy or walk a - 1 steps.
  • Off-by-one on afterB: Forgetting the final .next after reaching the node at index b.
  • Forgetting to find tail2: The connection list2_tail → afterB is easy to miss if you only set prevA → list2.

Key Takeaways

  • “Splice list into list” = find the boundary pointers (prevA, afterB) + find the tail of the inserted list + three pointer rewirings
  • When the head can never be removed, a dummy node is optional but can simplify uniform traversal
  • Constraints like a >= 1 and b < n - 1 eliminate edge cases – always read them carefully

References

Template Reference