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.