Two Pointer Merge — Sorted Structures

Merging sorted linked lists or arrays is the same walk: compare heads, advance the smaller side, append to output.

Try this in Python

def merge_sorted(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    out: list[int] = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out


print(merge_sorted([1, 4], [2, 3]))

Key takeaways

• Time O(n+m), space O(n+m) for new list.
• In-place merge of arrays is harder; interviews often use extra space first.
• Master the simple merge first.