AlgoMaster Logo

Merge In Between Linked Lists

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have two singly linked lists. We need to cut out a chunk from list1 (from index a to index b, inclusive) and stitch list2 into that gap. It is like splicing a new segment of rope into the middle of an existing one.

The constraints fix one detail that simplifies everything: a >= 1 and b < list1.length - 1. We never remove the first node or the last node of list1, so there is always a node before the cut and a node after the cut. We never have to handle the head or tail of list1 disappearing.

That leaves two anchor points to find in list1: the node right before position a (where list2's head attaches), and the node right after position b (where list2's tail attaches). With those two anchors in hand, the rest is pointer rewiring.

Key Constraints:

  • 3 <= list1.length <= 10^4 → With n up to 10,000, a single linear pass is more than fast enough. A linked list only supports sequential traversal anyway, so a linear walk is the natural fit.
  • 1 <= a <= b < list1.length - 1 → The cut always happens in the interior, never at the head or tail. list1's head is always the answer's head, and there is always at least one node after position b.
  • 1 <= list2.length <= 10^4 → list2 is never empty, so there is always something to insert.

Approach 1: Collect into Array

Intuition

Set the pointers aside and work with positions instead. Dump every node into an array, drop the ones from index a to b, splice list2's nodes into that gap, then walk the combined array and re-link the nodes in order.

Arrays support random access and slicing, so the removal and insertion become index arithmetic rather than careful pointer surgery. The relinking step at the end converts the array back into a singly linked list.

Algorithm

  1. Traverse list1 and collect all nodes into an array called nodes1.
  2. Traverse list2 and collect all nodes into an array called nodes2.
  3. Build a new result array by taking nodes1[0..a-1], then all of nodes2, then nodes1[b+1..end].
  4. Link the nodes in the result array sequentially: for each node, set its next to the following node in the array.
  5. Set the last node's next to null.
  6. Return the first node in the result array.

Visualization and Code

Loading animation...

This is correct but stores every node in arrays, using O(n + m) extra space. The next approach drops the arrays entirely: walk list1 to find the two anchor points, find list2's tail, and redirect two pointers in place.

Approach 2: Direct Pointer Manipulation

Intuition

A singly linked list is already a chain of pointers, so there is no need to tear it apart and rebuild it. Redirecting two connections is enough: the node at position a-1 should point to the head of list2, and the tail of list2 should point to the node at position b+1. The nodes from position a to b become unreachable from the head and are reclaimed by garbage collection.

A singly linked list is defined entirely by its next pointers. Setting beforeCut.next = list2 makes the nodes at positions a through b unreachable from the head, and setting list2Tail.next = afterCut closes the new chain back onto the kept portion of list1. The result is one connected list: the original nodes before position a, then all of list2, then the original nodes from position b+1 onward. No new nodes are created and no data is copied, so the only extra memory is a few pointer variables.

Algorithm

  1. Traverse list1 to position a-1. Save this node as beforeCut.
  2. Continue traversing from beforeCut to position b+1. Save this node as afterCut.
  3. Traverse list2 to its last node. Save this as list2Tail.
  4. Set beforeCut.next = list2 (connect the left side to list2's head).
  5. Set list2Tail.next = afterCut (connect list2's tail to the right side).
  6. Return list1's head (it never changes since a >= 1).

Visualization and Code

Loading animation...