Pattern visualizer
Merge Two Sorted Lists
Because both lists are already sorted, the smallest value not yet placed in the output has to be sitting at the front of one of the two lists — there's no need to look any deeper than the two current heads. So compare l1 and l2's current nodes, attach whichever is smaller to the output, and advance only that list's pointer; repeat until one list runs out, then splice on whatever's left of the other. Reach for it whenever combining two sorted sequences. Animated on: Merge two sorted lists [1,2,4] and [1,3,4] into one sorted output.
Linked List
step 1 / 8
1
[0]2
[1]4
[2]1
[3]3
[4]4
[5]line 2
Input: l1=[1,2,4] at idx0-2, l2=[1,3,4] at idx3-5. l1 at idx0(1), l2 at idx3(1).
Pseudocode
1FUNCTION mergeTwoLists(l1, l2):2 make a dummy start node; tail = dummy3 WHILE both l1 and l2 still have nodes:4 IF l1's value < l2's value: attach l1's node after tail; move l1 forward5 ELSE: attach l2's node after tail; move l2 forward6 tail = the node after tail7 END WHILE8 attach whichever list still has nodes after tail9 RETURN the node after dummy10END FUNCTION
← / → step · space play · Home restart