Leetcode 1669. Merge In Between Linked Lists

Problem

You are given two singly linked lists: list1 and list2. You are also given two integers a and b where 0 <= a <= b < length of list1.

Your task is to remove the nodes in list1 from position a to position b (inclusive, using 0-based indexing), and insert the entire list2 in their place.

Return the head of the modified list1.

Requirements

1. Remove all nodes from position a to position b (inclusive) in list1
2. Insert the entire list2 in place of the removed nodes
3. The resulting list should maintain proper linked list connections
4. Return the head of the modified list

Constraints

• 3 ≤= length of list1 ≤= 104
• 1 ≤= length of list2 ≤= 104
• 1 ≤= node values ≤= 106
• 0 ≤= a ≤= b < length of list1 - 1
• The positions a and b are guaranteed to be valid

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] Explanation: We remove nodes at positions 3 and 4 (values 6 and 9). Then we insert list2 between position 2 (value 13) and position 5 (value 5).

Example 2:

Input: list1 = [0, 1, 2, 3, 4, 5], a = 2, b = 2, list2 = [100, 101] Output: [0, 1, 100, 101, 3, 4, 5] Explanation: We remove only the node at position 2 (value 2) and insert list2 in its place.

Example 3:

Input: list1 = [0, 1, 2, 3, 4], a = 2, b = 3, list2 = [50] Output: [0, 1, 50, 4] Explanation: Remove positions 2 and 3 (values 2 and 3), then insert list2 which contains only one node.

Hint 1: Finding Connection Points You need to identify two key nodes: the node just before position a and the node just after position b. These will be your connection points for splicing in list2.

Hint 2: Traversal Strategy Traverse list1 to find the node at position a - 1 (the node before the removal section). Continue traversing to find the node at position b + 1 (the node after the removal section). You can do this in a single pass.

Hint 3: Finding the Tail of list2 To connect list2 properly, you'll need to find the tail node of list2 so you can link it to the node after position b in list1.

Full Solution ` class ListNode: def init(self, val=0, next=None): self.val = val self.next = next

def mergeInBetween(list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode: # Find the node just before position a node_before_a = list1 for _ in range(a - 1): node_before_a = node_before_a.next

# Find the node at position b (we'll skip past it)
node_at_b = node_before_a
for _ in range(b - a + 2):  # Move from position a-1 to b+1
    node_at_b = node_at_b.next

# Connect the node before position a to the head of list2
node_before_a.next = list2

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

# Connect the tail of list2 to the node after position b
tail_of_list2.next = node_at_b

return list1

`

Explanation:

The solution works in several steps:

1. Find the connection point before removal: We traverse to position a - 1 to find the node that comes just before the section we want to remove.
2. Find the connection point after removal: Starting from the node before a, we traverse b - a + 2 steps to reach the node after position b. This node will be connected to the end of list2.
3. Connect list2: We attach the head of list2 to the node before position a.
4. Find list2's tail: We traverse list2 to find its last node.
5. Complete the connection: We connect the tail of list2 to the node that was after position b.

Time Complexity: O(n + m) where n is the length of list1 and m is the length of list2. We traverse portions of both lists once.

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