Merge two sorted linked lists into one sorted list by splicing nodes (e.g. 1->3->5 and 2->4->6 -> 1->2->3->4->5->6).
Use a dummy head and a tail pointer; repeatedly attach the smaller of the two front nodes and advance that list, then attach whatever remains. Using a dummy node avoids special-casing the first element. O(n + m) time, O(1) extra space.
public static Node merge(Node a, Node b) {
Node dummy = new Node(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b;
return dummy.next;
}function merge(a, b) {
const dummy = new Node(0);
let tail = dummy;
while (a && b) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a || b;
return dummy.next;
}def merge(a, b):
dummy = Node(0)
tail = dummy
while a and b:
if a.val <= b.val:
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next
tail.next = a or b
return dummy.nextMerging sorted lists is the linked-list analog of the merge step in merge sort and of combining ordered event streams.
What role does the dummy head node play, and what breaks without it?