0076EasyLinked ListRecursion

Splice Index Card Chains

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two archive drawers each hold a chain of index cards. Every card carries one signed shelf offset and points at the next card in the same drawer, so a drawer is a single file of cards. Walking a drawer from its front card, the offsets already run from smallest to largest, and a drawer may hold no cards at all.

Card pointers cannot be handed over directly, so each chain arrives as a plain JSON list of its offsets in walking order, front card first: [-4, 0, 7] is a front card holding -4, behind it a card holding 0, and behind that a card holding 7. Give your answer back in the same form.

Weave the two chains into one file of cards whose offsets still run from smallest to largest. Every card is kept, so an offset held in both drawers shows up twice in the answer. Reuse the cards you were handed: compare the two front cards, detach the one holding the smaller offset, attach it behind the growing answer, and carry on. Do not pool the offsets and sort them. Walk each chain once, in O(m + n) steps, with only a constant amount of bookkeeping beyond the chain you hand back. When both drawers are bare, hand back an empty chain.

Examples

Example 1

Input: chain1 = [-4, 0, 7], chain2 = [-9, 0, 1]
Output: [-9, -4, 0, 0, 1, 7]

The front cards hold -4 and -9, so the -9 card is detached first; the offset 0 sits in both drawers and is therefore kept twice.

Example 2

Input: chain1 = [], chain2 = []
Output: []

Neither drawer holds a card, so there is nothing to attach anywhere.

Example 3

Input: chain1 = [], chain2 = [-100, 3]
Output: [-100, 3]

One drawer is bare, so the surviving file is exactly the other drawer's cards in their existing walking order.

Constraints

0 <= chain1.length <= 50
0 <= chain2.length <= 50
-100 <= chain1[i], chain2[i] <= 100
Both chain1 and chain2 are already in non-decreasing order

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def splice_chains(chain1: list[int], chain2: list[int]) -> list[int]:

Java

public int[] spliceChains(int[] chain1, int[] chain2)

The intended approach

Time O(m + n)Space O(1) beyond the returned chain

Only the two front cards can supply the next offset of the woven file, so hold a cursor on each chain and always detach whichever front offset is smaller, breaking ties toward the first chain. When one cursor runs off its chain, the other chain is already ordered, so attach the rest of it as-is. Each card is looked at once and the bookkeeping is two cursors.

Pythonentry point: splice_chains

def splice_chains(chain1, chain2):
    woven = []
    i = 0
    j = 0
    while i < len(chain1) and j < len(chain2):
        if chain1[i] <= chain2[j]:
            woven.append(chain1[i])
            i += 1
        else:
            woven.append(chain2[j])
            j += 1
    while i < len(chain1):
        woven.append(chain1[i])
        i += 1
    while j < len(chain2):
        woven.append(chain2[j])
        j += 1
    return woven

The obvious version

Ignore the ordering already present: dump both chains into one pool and sort the pool. O((m + n) log(m + n)).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_splice_chains(chain1, chain2):
    pooled = list(chain1) + list(chain2)
    pooled.sort()
    return pooled

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in