Merge two sorted lists

Problem Merge two sorted linked lists into one sorted list by splicing their nodes (no new nodes for values).

Input / Output

• Input: heads l1, l2 of sorted lists.
• Output: head of the merged sorted list.

Constraints

• Up to 50 nodes each classically, but the technique must scale; O(m+n) time, O(1) extra space iteratively.

Example

• 1→2→4 and 1→3→4 → 1→1→2→3→4→4.

Expected approach

• Dummy head + tail pointer: repeatedly attach the smaller current node and advance that list; attach the non-empty remainder at the end. O(m+n)/O(1). The recursive version is elegant but O(m+n) stack. This is the building block for merge-k-lists (heap or pairwise divide-and-conquer) — a frequent follow-on.