Back to DSA
Merge Two Sorted Lists
mediumTwo sorted singly linked lists are provided. Combine them into a single sorted list by interleaving the nodes from both input lists (do not create new nodes, reuse the existing ones). Return the head of the unified sorted list.
Examples
Example 1:
Input:
list1 = [2,5,9], list2 = [1,4,7]Output:
[1,2,4,5,7,9] Example 2:
Input:
list1 = [], list2 = [3]Output:
[3]Hints
class Solution {
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;
return dummy.next;
}
}Time complexity
O(n + m)Space complexity
O(1)