Overview
Merge two already-sorted lists into one sorted list using two pointers, one per list.
Analogy
Two sorted stacks of playing cards: compare top cards, take the smaller, repeat.
Step-by-step
- i=0, j=0 pointing to heads of both lists.
- While both have elements: if a[i]<=b[j]: take a[i], i++; else take b[j], j++.
- Append leftover elements from whichever list remains.
- Total: O(n+m) time, O(n+m) space.
Visual
A=[1,3,5], B=[2,4,6] → compare 1<2,take1; 3>2,take2; ... → [1,2,3,4,5,6]
Common mistakes
- Forgetting to append the remaining tail of one list.
- Mutating the input lists instead of building a new list.
Practice questions
- Merge k sorted lists (use a min-heap).
- Merge in-place without extra space (harder: O(1) space O(n log n) time).
AI Wisdom