Merge Two Sorted Lists

Problem

Merge two sorted linked lists into one sorted list by splicing nodes (no new allocations).

Example

l1 = 1->2->4, l2 = 1->3->4
Output: 1->1->2->3->4

Constraints

• 0 ≤ length ≤ 50 each

Follow-up

Merge k sorted lists. What data structure brings it to O(N log k)?