Merge In Between Linked Lists

How it works

We can solve this problem recursively by reducing the indices a and b as we move deeper into list1. When a reaches 1, we have found the insertion point and can attach list2. We then continue recursing with list2's tail to skip over the nodes that should be removed (while b counts down). When b reaches 0, we have passed all nodes to remove and can connect the tail of list2 to the remaining nodes of list1.

Steps

1. If a == 1, we are at the insertion point:
   • Save list1.next as nxt.
   • Set list1.next = list2.
   • Traverse to the end of list2 to find its tail.
   • Recursively call the function with nxt, a = 0, b - 1, and the tail of list2.
   • Return list1.
2. If b == 0, we have skipped all nodes to remove:
   • Set list2.next = list1.next to connect the tail of list2 to the rest of list1.
   • Return list1.
3. Otherwise, recurse on list1.next with a - 1 and b - 1.
4. Return list1.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(n) for recursion stack.

Where n is the length of the first list and m is the length of the second list.

Things to watch for

Off-by-One Errors When Finding the Insertion Point

The node at index a - 1 should point to list2, and the tail of list2 should point to the node at index b + 1. Using index a or b directly results in incorrect splicing.

Forgetting to Find the Tail of list2

After connecting the node before position a to list2, you must traverse list2 to find its tail and connect it to the remaining nodes of list1. Skipping this step leaves the merged list incomplete.

Not Handling the Removed Nodes

The nodes from index a to b are no longer part of the result list. In languages without garbage collection, failing to properly handle these nodes can cause memory leaks.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        if a == 1 :
            nxt = list1.next
            list1.next = list2
            while list2.next:
                list2 = list2.next
            self.mergeInBetween(nxt, 0, b - 1, list2)
            return list1

        if b == 0:
            list2.next = list1.next
            return list1

        self.mergeInBetween(list1.next, a - 1, b - 1, list2)
        return list1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        if (a == 1) {
            ListNode* nxt = list1->next;
            list1->next = list2;

            while (list2->next) {
                list2 = list2->next;
            }
            mergeInBetween(nxt, 0, b - 1, list2);
            return list1;
        }

        if (b == 0) {
            list2->next = list1->next;
            return list1;
        }

        mergeInBetween(list1->next, a - 1, b - 1, list2);
        return list1;
    }
};