Splice One Linked List Into Another Between Positions a and b

Reported in interviews at Point72

Problem statement

You are given two singly linked lists, list1 and list2, and two integers $a$ and $b$. Remove the $a$-th through $b$-th nodes (inclusive, 0-indexed) of list1 and splice list2 into that gap, so the result is:

$$\text{list1}_0 \rightarrow \cdots \rightarrow \text{list1}_{a-1} \rightarrow \text{list2}_0 \rightarrow \cdots \rightarrow \text{list2}_m \rightarrow \text{list1}_{b+1} \rightarrow \cdots$$

Return the head of the merged list. (This is LeetCode 1669, Merge In Between Linked Lists.)

Example

merge_in_between([1, 2, 3], 0, 2, [9]) -> [9]
Show hint

In a singly linked list, which nodes do you actually need a reference to in order to cut out a segment and insert another list?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems