Merge two sorted linked lists into one sorted list. This is the linked-list version of the merge step in merge sort.
# List 1: 1 → 2 → 4
# List 2: 1 → 3 → 4
# Merged: 1 → 1 → 2 → 3 → 4 → 4
Use a dummy node to simplify the logic. Compare the heads of both lists and always attach the smaller one.
Time: O(n + m), Space: O(1) — we're just rearranging pointers, not creating new nodes.
📋 Instructions
Implement `merge_two_lists(l1, l2)` that merges two sorted lists.
Merge [1,2,4] and [1,3,4], then print all values of the merged list.
Create a dummy node. Use a tail pointer. While both lists have nodes, compare and attach the smaller one to tail.next. Advance tail and the chosen list's pointer. Attach remaining nodes at the end.