Over the weekend I was curious about efficiently merging multiple sorted iterators together, and for them to be in sorted order. This is quite like a challenge on HackerRank:
You’re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty.
I may have cheated a bit by printing, rather than returning the items. However I don't mind that much about the HackerRank challenge.
I managed to do this in about \$O(3l)\$ space and \$O(l(2+n))\$ time. So \$O(l)\$ and \$O(ln)\$. Where \$l\$ is the amount of lists, and \$n\$ is the amount of data.
import operator
import functools
def from_iterable(fn):
@functools.wraps(fn)
def inner(*args):
return fn(args)
inner.from_iterable = fn
return inner
@from_iterable
def merge(sources):
sources = {
id_: iter(source)
for id_, source in enumerate(sources)
}
values = {}
for id_, source in list(sources.items()):
try:
values[id_] = next(source)
except StopIteration:
del sources[id_]
by_value = operator.itemgetter(1)
while sources:
id_, minimum = min(values.items(), key=by_value)
try:
values[id_] = next(sources[id_])
except StopIteration:
del values[id_], sources[id_]
yield minimum
def iter_nodes(node):
while node is not None:
yield node.data
node = node.next
def MergeLists(headA, headB):
vals = merge.from_iterable(iter_nodes(l) for l in (headA, headB))
print(' '.join(str(i) for i in vals), end='')
A bit overkill for the HackerRank challenge. But that wasn't the main reason for doing it.
Any and all reviews are welcome.
(value, id)
instead of a dictionary gives \$O(n \log l)\$ time complexity. \$\endgroup\$