Show problems as
Classic problem #21EasyLinked ListRecursion

Merge Two Sorted Lists

Real-world version: Splice Index Card Chains
Tracked in this browser only
Read Merge Two Sorted Lists on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstDummy Node Technique · Linked List, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def splice_chains(chain1: list[int], chain2: list[int]) -> list[int]:
Java
public int[] spliceChains(int[] chain1, int[] chain2)

More on the same topics