Merge In Between Linked Lists

medium linked list pointers

Problem

You get two singly linked lists, list1 with n nodes and list2 with m nodes, plus two indices with 1 ≤ a ≤ b < n − 1. Delete list1's nodes from index a through index b and wire all of list2 into the gap: node a − 1 must point at list2's head, and list2's last node must point at node b + 1. Return list1's head.

Inputlist1 = 10 → 1 → 13 → 6 → 9 → 5, a = 3, b = 4, list2 = 100 → 101 → 102

Output10 → 1 → 13 → 100 → 101 → 102 → 5

Nodes 6 and 9 (indices 3..4) are cut out; node 13 now points at 100, and 102 points at 5.

list1 (comma-separated)

list2 (comma-separated)

def merge_in_between(list1, a, b, list2):
    prev = list1
    for _ in range(a - 1):
        prev = prev.next
    after = prev
    for _ in range(b - a + 2):
        after = after.next
    prev.next = list2
    tail = list2
    while tail.next:
        tail = tail.next
    tail.next = after
    return list1

function mergeInBetween(list1, a, b, list2) {
  let prev = list1;
  for (let i = 0; i < a - 1; i++) prev = prev.next;
  let after = prev;
  for (let i = 0; i < b - a + 2; i++) after = after.next;
  prev.next = list2;
  let tail = list2;
  while (tail.next) tail = tail.next;
  tail.next = after;
  return list1;
}

ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
    ListNode prev = list1;
    for (int i = 0; i < a - 1; i++) prev = prev.next;
    ListNode after = prev;
    for (int i = 0; i < b - a + 2; i++) after = after.next;
    prev.next = list2;
    ListNode tail = list2;
    while (tail.next != null) tail = tail.next;
    tail.next = after;
    return list1;
}

ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
    ListNode* prev = list1;
    for (int i = 0; i < a - 1; i++) prev = prev->next;
    ListNode* after = prev;
    for (int i = 0; i < b - a + 2; i++) after = after->next;
    prev->next = list2;
    ListNode* tail = list2;
    while (tail->next) tail = tail->next;
    tail->next = after;
    return list1;
}

Explanation

Only two wires in list1 ever change: the next pointer of node a − 1 (the last node we keep on the left) and the next pointer of list2's tail, which must reach node b + 1 (the first node we keep on the right). Everything else stays exactly where it is, so the whole problem reduces to finding those two boundary nodes.

First, walk a pointer prev forward a − 1 steps from list1's head so it lands on index a − 1. The constraint 1 ≤ a guarantees this predecessor exists, which is why no dummy node is needed.

Next, keep walking from prev another b − a + 2 steps to reach index b + 1; call this node after. The constraint b < n − 1 guarantees after is a real node, never null. Now perform the cut: prev.next = list2. Nodes a..b become unreachable — they are simply dropped (garbage-collected in Python/JS/Java, leaked or freed separately in C++).

Finally, walk a pointer tail down list2 to its last node and stitch the gap closed with tail.next = after. The list is whole again: left part of list1, then all of list2, then the right part of list1.

On the default example, prev walks 2 steps to node 13 (index 2), after walks 3 more steps to node 5 (index 5), the cut drops 6 and 9, tail walks to 102, and the stitch yields 10 → 1 → 13 → 100 → 101 → 102 → 5.

Each pointer traverses its list at most once — prev and after cover list1, tail covers list2 — so the time is O(n + m), and we only ever hold three extra pointers, so the space is O(1).

Time: O(n + m) Space: O(1)