Problem
You are given the heads of two sorted linked lists. Merge them into one sorted linked list and return its head.
Example
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]Solution
Use a dummy node to simplify edge cases. Walk both lists, attaching the smaller node to the result.
def merge_two_lists(l1, l2):
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.nextfunction mergeTwoLists(l1, l2) {
const dummy = { next: null };
let tail = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = l1 || l2;
return dummy.next;
}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}Complexity
- Time: O(n + m)
- Space: O(1)
Explanation
The dummy node is a classic linked list trick. It removes the need to handle “is this the first node?” logic. We always have somewhere to attach the next node.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?