Problem Description

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

Your task is to remove a range of nodes from list1 (specifically from the a-th node to the b-th node, inclusive) and replace them with the entire list2.

The nodes in linked lists are 1-indexed, meaning:

• The a-th node is the node at position a (counting from 1)
• The b-th node is the node at position b (counting from 1)
• You need to remove all nodes from position a to position b (inclusive)

After removing these nodes, you should insert all nodes from list2 in their place, maintaining the connections properly.

For example, if list1 is [0,1,2,3,4,5], a = 3, b = 4, and list2 is [1000000,1000001,1000002]:

• You would remove nodes at positions 3 and 4 (which have values 2 and 3)
• Insert list2 in their place
• The result would be [0,1,1000000,1000001,1000002,4,5]

The function should return the head of the modified list1 after performing this merge operation.

Intuition

To solve this problem, we need to think about what connections we need to modify in the linked list structure.

The key insight is that we need to identify four critical points:

1. The node just before position a (let's call it the "pre-removal" node)
2. The node at position b (the last node to be removed)
3. The head of list2 (the start of what we're inserting)
4. The tail of list2 (the end of what we're inserting)

Once we have these points, the operation becomes straightforward:

• Connect the "pre-removal" node to the head of list2
• Connect the tail of list2 to the node that comes after position b

To find these positions, we can use two pointers traversing from the head of list1:

• One pointer p moves a-1 steps to reach the node just before position a
• Another pointer q moves b steps to reach the node at position b

The reason we move p only a-1 steps is because we need to keep the connection point before the removal range. We need access to this node so we can redirect its next pointer to list2.

For q, we move exactly b steps because we need to know what comes after the last removed node (which is q.next), so we can connect the tail of list2 to it.

Finally, we traverse list2 to find its tail node, then complete the connections. This approach modifies the original list1 in-place by splicing in list2 at the correct position.

Learn more about Linked List patterns.

Solution Approach

The solution uses a two-pointer simulation approach to perform the merge operation. Here's the step-by-step implementation:

Step 1: Initialize two pointers

p = q = list1

Both pointers p and q start at the head of list1. These will help us locate the critical connection points.

Step 2: Position pointer p before the removal range

for _ in range(a - 1):
    p = p.next

Move p forward (a-1) times. After this loop, p points to the node just before the a-th node. This is crucial because we need to modify p.next to point to list2.

Step 3: Position pointer q at the end of the removal range

for _ in range(b):
    q = q.next

Move q forward b times from the head. After this loop, q points to the b-th node (the last node to be removed).

Step 4: Connect the pre-removal node to list2

p.next = list2

This disconnects the nodes from position a to b and starts the connection to list2.

Step 5: Find the tail of list2

while p.next:
    p = p.next

Since p.next now points to list2, we traverse through list2 until we reach its tail node (where p.next becomes None).

Step 6: Complete the connection

p.next = q.next
q.next = None

Connect the tail of list2 to the node that came after the b-th node in the original list1. Setting q.next = None helps clean up the removed segment (though this is optional since those nodes are no longer reachable).

Step 7: Return the modified list

return list1

The head of list1 remains unchanged, so we return it as the result.

Time Complexity: O(a + b + m) where m is the length of list2. We traverse to position a-1, then to position b, and finally through all nodes of list2.

Space Complexity: O(1) as we only use a constant amount of extra space for the pointers.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• list1: 10 → 20 → 30 → 40 → 50
• list2: 100 → 200
• a = 2, b = 3 (remove nodes at positions 2 and 3)

Goal: Remove nodes 20 and 30 from list1 and insert list2 in their place.

Step 1: Initialize pointers

p = q = list1
Both p and q point to node 10

Step 2: Position p before removal range (move a-1 = 1 time)

p moves 1 step: p now points to node 10
list1: 10 → 20 → 30 → 40 → 50
       p

Step 3: Position q at end of removal range (move b = 3 times)

q moves 3 steps: 10 → 20 → 30
list1: 10 → 20 → 30 → 40 → 50
       p         q

Step 4: Connect p.next to list2

p.next = list2 (node 100)
Now: 10 → 100 → 200
     p
(Nodes 20 and 30 are disconnected)

Step 5: Find tail of list2

Move p through list2:
p: 10 → 100 → 200
        p     p (final position)

Step 6: Complete the connection

p.next = q.next (node 40)
Final: 10 → 100 → 200 → 40 → 50

Result: The modified list is 10 → 100 → 200 → 40 → 50

The nodes at positions 2 and 3 (values 20 and 30) have been successfully replaced with the entire list2 (100 → 200).

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n), where m is the length of list1 and n is the length of list2.

The time complexity breaks down as follows:

• First loop: O(a) iterations to position pointer p at index a-1
• Second loop: O(b) iterations to position pointer q at index b
• Third loop: O(n) iterations to traverse through all nodes of list2 to find its tail
• Since a and b are at most m-1, the worst case for the first two loops is O(m)
• Total: O(m) + O(n) = O(m + n)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Two pointers p and q that reference existing nodes
• No additional data structures are created
• The operation modifies the existing linked lists in-place by adjusting pointers

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Pointer Positioning

The Pitfall: The most common mistake is incorrectly positioning the before_removal_node pointer. Many developers mistakenly move it a times instead of a-1 times, which would position it at the a-th node rather than the node before it.

Incorrect Code:

# WRONG: This moves the pointer TO position a, not BEFORE it
for _ in range(a):  # Should be (a-1)
    before_removal_node = before_removal_node.next

Why This Fails:

• If you move a times, before_removal_node points to the first node that should be removed
• When you then set before_removal_node.next = list2, you're keeping one node that should have been removed
• This results in an extra node in the final list

The Solution: Always remember that to insert at position a, you need to access the node at position a-1. Use range(a-1) for the first pointer.

2. Edge Case: When a = 1 (Removing from the Beginning)

The Pitfall: When a = 1, the code tries to move the pointer (a-1) = 0 times, which means before_removal_node stays at the head. This works correctly for the connection but conceptually might be confusing.

Potential Issue: If someone modifies the code without understanding this edge case, they might add special handling that breaks the solution:

# WRONG: Unnecessary special case handling
if a == 1:
    # Trying to handle first node removal differently
    temp = list1
    for _ in range(b):
        temp = temp.next
    list1 = list2  # This doesn't work! We lose reference to return correct head

The Solution: Trust the algorithm - when a = 1:

• before_removal_node stays at the head (moved 0 times)
• after_removal_node moves to position b
• Setting before_removal_node.next = list2 correctly removes nodes 1 through b
• The original head is preserved and returned correctly

3. Not Handling Empty list2

The Pitfall: If list2 is empty (null), the traversal loop while before_removal_node.next: won't execute, and before_removal_node remains pointing to the node before position a.

Problematic Scenario:

# If list2 is None or empty:
before_removal_node.next = list2  # Sets to None
while before_removal_node.next:   # Loop doesn't execute
    before_removal_node = before_removal_node.next
before_removal_node.next = after_removal_node.next  # Still works correctly!

Why It Actually Works: The code handles this gracefully because when list2 is None, the connection still works properly - we're essentially just removing nodes without inserting anything.

Potential Enhancement (if needed):

if list2:  # Only traverse if list2 exists
    before_removal_node.next = list2
    while before_removal_node.next:
        before_removal_node = before_removal_node.next
else:
    # Direct connection when list2 is empty
    pass  # The next line handles it
before_removal_node.next = after_removal_node.next

4. Confusion with 0-indexed vs 1-indexed Positions

The Pitfall: The problem statement uses 1-indexed positions (nodes are counted starting from 1), but the implementation treats a and b as if they follow this convention. Some developers might get confused and try to adjust for 0-indexing.

Wrong Adjustment:

# WRONG: Don't adjust if the problem already uses 1-indexing
for _ in range(a - 2):  # Incorrectly subtracting 2
    before_removal_node = before_removal_node.next

The Solution: Carefully read whether the problem uses 0-indexing or 1-indexing. In this case:

• Position 1 = first node
• Position 2 = second node
• To get to the node before position a, move (a-1) times from the head