## What is it? Merge two sorted singly linked lists into a single sorted linked list. An essential operation used in Merge Sort on linked lists. ## How it works - Use a dummy head node to simplify edge cases - Compare `l1.val` and `l2.val`; append the smaller node to the result list - Advance the pointer in the chosen list - When one list is exhausted, append the remainder of the other list directly - Return `dummy.next` ## When to use - Merge step in Merge Sort for linked lists - Merging k sorted lists (extend with a priority queue) - Any problem requiring ordered combination of two sorted sequences ## Key Points - O(n + m) time — visits each node exactly once - O(1) space — in-place pointer manipulation (no new nodes created) - Dummy head node eliminates the need for special-casing the first node - Recursive approach is elegant but uses O(n + m) stack space