Merge In Between Linked Lists - Video Solutions

Problem Overview: You are given two linked lists. In the first list, remove nodes from index a to b (inclusive) and insert the entire second list in that position. The task is to reconnect pointers so that list2 replaces that segment of list1 without creating new nodes.

Approach 1: Using Two Pointers (O(n) time, O(1) space)

This approach walks through list1 to find two critical nodes: the node right before index a and the node right after index b. Use iteration with a counter while maintaining pointers to these boundaries. Once found, connect the a-1 node to the head of list2, then traverse list2 to locate its tail. Finally connect that tail to the node after index b. The algorithm performs only pointer rewiring—no node copying or extra data structures—so the space complexity stays O(1). Time complexity is O(n + m), where n is the length of list1 and m is the length of list2. This pattern is common in two pointer linked list manipulation problems where you track boundaries and reconnect segments.

The key insight is that you never need to rebuild the list. You only identify the node before the cut and the node after the cut. Once those are known, the entire merge reduces to two pointer assignments. This keeps the algorithm linear and extremely memory efficient.

Approach 2: Recursive Approach (O(n + m) time, O(n) space)

A recursive strategy processes list1 node by node while keeping track of the current index. When the recursion reaches index a, instead of continuing down the original list, it returns the head of list2. The recursion skips nodes until index b and reconnects the tail of list2 with the remainder of list1. Conceptually this mirrors how recursion naturally rebuilds linked structures during stack unwinding.

This approach still visits each node once, giving O(n + m) time complexity. However, recursion introduces call stack overhead, so the auxiliary space becomes O(n). It is mainly useful for understanding structural transformations in linked lists and practicing pointer manipulation using recursion. In production or interview settings, iterative solutions are usually preferred for their constant space usage.

Recommended for interviews: The two-pointer approach is what interviewers typically expect. It shows you understand how to locate boundaries in a linked list and reconnect segments efficiently. Implementing it in O(n + m) time with O(1) extra space demonstrates strong pointer manipulation skills. Discussing the recursive version can still be useful to show deeper understanding of linked list transformations, but the iterative two-pointer method is the optimal and most practical solution.