How do you merge two sorted linked lists into one sorted list?
You use one pointer in each list and you always take the smaller of the two values in front of you, and you attach the chosen node to the tail of the answer.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def merge_two_lists(first, second):
dummy = Node(0)
tail = dummy
while first is not None and second is not None:
if first.value <= second.value:
tail.next = first
first = first.next
else:
tail.next = second
second = second.next
tail = tail.next
# One of the lists is finished, so the rest of it goes on the end.
tail.next = first if first is not None else second
return dummy.next
So how does it work? The dummy node gives you a head that always exists, and the tail pointer says where the next chosen node goes. At each step you compare the value in front of the first list with the value in front of the second list, and you attach the smaller one to the tail and then move that list's pointer on.
And the loop stops when one of the lists runs out. At that point the other list is already in order, so you can attach the whole of it and you are done. That is why the last line is there and why the loop does not need to handle the tail of both lists separately.
the first list 1 -> 3 -> 5
the second list 2 -> 4 -> 6
the answer 1 -> 2 -> 3 -> 4 -> 5 -> 6
And the complexity is O of m plus n for the time, where m and n are the lengths of the two lists, and O of 1 for the space, because no new nodes are made. The existing nodes are simply re-linked, which is the good part.
And there is one detail worth knowing about. The comparison uses <= and not <. With <= the node from the first list is taken when the values are the same, and that keeps the merge stable, so equal values keep the order they started in.
So the rule to remember is this. Take the smaller front value, and when one list ends, attach the other one whole.
The next two questions in this topic show the recursive version and the version for k lists.