DSA problem
Merge In Between Linked Lists
You are given two linked lists, list1 and list2, along with two integer indices a and b. Your task is to remove the nodes of list1 from position a to position b inclusive, and splice the entire list2 into that gap, then return the head of the resulting combined list.
Conceptually you need three reference points in list1: the node just before position a (call it the prefix tail), the node at position b (the last node to be removed), and the node just after position b (the suffix head). Once you have these, the rewiring is straightforward: connect the prefix tail to the head of list2, and connect the tail of list2 to the suffix head.
The constraints guarantee 1 <= a <= b, so the node before position a always exists — you never have to deal with removing the head of list1. That keeps the logic clean and avoids any dummy-node bookkeeping.
The optimal approach is a single linear scan. Walk list1 to find the node at index a - 1 and the node at index b + 1 (or null if b is the last index). Then walk list2 to its tail. Finally perform two pointer assignments to stitch everything together. This runs in O(m + k) time, where m is the length of list1 and k the length of list2, using O(1) extra space.
Examples
list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002][10,1,13,1000000,1000001,1000002,5]list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004][0,1,1000000,1000001,1000002,1000003,1000004,6]list1 = [0,1,2], a = 1, b = 1, list2 = [9,9][0,9,9,2]Constraints
- 3 <= list1.length <= 10^4
- 1 <= a <= b < list1.length - 1
- 1 <= list2.length <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.