You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. Return the head of the merged linked list.
Example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
The number of nodes in both lists is in the range [0, 50].-100 <= Node.val <= 100Use a dummy head node to simplify edge cases at the start of the list — it removes the need for a special first-node check.
A recursive alternative is often considered more elegant: whichever list's current head is smaller becomes the result's head, with its .next set to the recursive merge of the remainder — at the cost of O(m+n) recursion-stack space versus the iterative version's O(1).
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2; // attach remaining
return dummy.next;
}Time: O(m+n) · Space: O(1)