#1669

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Merge In Between Linked Lists

Merge a second linked list into a first by removing a specified range of nodes, testing precise pointer updates and list integrity.

linked list

Problem Statement

Given two singly linked lists list1 and list2, and two integers a and b, remove nodes from index a to index b in list1 and insert list2 in their place. Maintain the relative order of remaining nodes and ensure all pointer connections are correct.

Return the modified list1 after the merge. Example: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] results in [10,1,13,1000000,1000001,1000002,5]. Constraints guarantee valid indices and non-empty lists.

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]

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]

The blue edges and nodes in the above figure indicate the result.

Constraints

3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104

Solution Approach

Locate insertion boundaries

Traverse list1 to identify the node just before index a and the node at index b. These nodes define the boundaries for the merge, critical to correct pointer manipulation.

Disconnect and merge

Detach the sublist from a to b by adjusting pointers, then connect the start of list2 to the node before a, and the end of list2 to the node after b. This preserves list integrity.

Validate connections and return

Ensure the new connections correctly link all nodes, avoiding cycles or orphaned nodes. Return the modified head of list1 for verification.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(1)

Time complexity is O(n + m) since both lists are traversed once; space complexity is O(1) because the merge uses in-place pointer adjustments without extra structures.

What Interviewers Usually Probe

Watches for correct identification of pre-a and post-b nodes.
Checks for in-place pointer updates without creating new nodes unnecessarily.
Confirms understanding of linked-list edge cases and index handling.

Common Pitfalls or Variants

Common pitfalls

Failing to connect the last node of list2 to the node after b.
Incorrectly calculating indices a and b, leading to wrong nodes removal.
Accidentally creating cycles or losing part of list1 during pointer reassignment.

Follow-up variants

Merge multiple segments from list1 with different lists in sequence.
Perform the merge in a circular linked list scenario.
Merge with additional constraints like preserving a sorted order.

FAQ

What is the main challenge in Merge In Between Linked Lists?

The challenge is correctly updating pointers to remove nodes a through b and insert list2 without breaking the list.

Can this be done without extra space?

Yes, the merge is done in-place using O(1) extra space by adjusting existing pointers.

How do I verify the merge is correct?

Check that the nodes before a connect to the head of list2, and the tail of list2 connects to the node after b.

Does the order of list1 outside the removed segment change?

No, all nodes outside the removed segment retain their original relative order.

Why is linked-list pointer manipulation important here?

This problem tests precise pointer updates to remove and insert segments without data loss, a core linked-list manipulation pattern.

terminal

Solution

Solution 1: Simulation

We can directly simulate the operations described in the problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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:
        p = q = list1
        for _ in range(a - 1):
            p = p.next
        for _ in range(b):
            q = q.next
        p.next = list2
        while p.next:
            p = p.next
        p.next = q.next
        q.next = None
        return list1

Continue Practicing

#1670 design front middle back queue #1721 swapping nodes in a linked list #1797 design authentication manager