0

I have two lists as follows:

l1 = [1,3,5,7] and l2 = [2,4,6]

how can I get this output l3 = [1,2,3,4,5,6,7] ,that is, inserting the first entry from l2 as second entry in l1 and so on. Thanks in advance

jpp
  • 159,742
  • 34
  • 281
  • 339
greatunarine1
  • 11
  • Use can use a modified version of iterations of insertion sort. – Haris Mar 24 '18 at 00:02
  • Since the lists are already sorted, you simply merge the lists. If you want to insert, use the list `insert` method. Where are you stuck? – Prune Mar 24 '18 at 00:04
  • I think this is more "Unclear" than a dup. OP should confirm (a) whether input lists are always sorted; (b) whether output result is required to be sorted. – jpp Mar 24 '18 at 00:27
  • @greatunarine1, will you be able to advise on the 2 questions above? – jpp Mar 24 '18 at 00:28

2 Answers2

0

Without assuming the input lists are sorted, or requiring the output be sorted, you can use itertools for this.

from itertools import zip_longest, chain

l1 = [1,3,5,7]
l2 = [2,4,6]

res = list(filter(None, chain.from_iterable(zip_longest(l1, l2))))

# [1, 2, 3, 4, 5, 6, 7]

Explanation

  • Use zip_longest to iterate lists of unequal length pairwise.
  • Use chain.from_iterable to efficiently chain the list of lists.
  • Use filter(None, ...) to remove the final None element.
jpp
  • 159,742
  • 34
  • 281
  • 339
  • 1
    `chain.from_iterable([i, j] for i, j in zip_longest(l1, l2))` is a slow way to write `chain.from_iterable(zip_longest(l1, l2))`; no need for the effectively no-op genexpr. This does assume the OP wants intercalation, not combining of arbitrary sorted inputs (that is, they *don't* want `l1 = [1, 2, 3]; l2 = [4, 5, 6]` to produce `l3 = [1, 2, 3, 4, 5, 6]`, but instead would want `l3 = [1, 4, 2, 5, 3, 6]`). – ShadowRanger Mar 24 '18 at 00:17
  • 1
    All answers provided above works very well. Thanks – greatunarine1 Mar 24 '18 at 00:25
0

Here is one way that relies on the input lists being sorted in advance in an alternating order like your example, such that you actually want to intercalate them, rather than doing any type of sorted merge.

And that the value None would never serve as a true value among your lists.

In [12]: from itertools import chain, ifilter, izip_longest 

In [13]: list(ifilter(lambda x: x is not None, chain(*izip_longest(l1, l2))))
Out[13]: [1, 2, 3, 4, 5, 6, 7]
ely
  • 74,674
  • 34
  • 147
  • 228
  • Assuming intercalation is what the OP wants this is fine, but I'd suggest replacing `chain(*izip_longest(l1, l2))` with `chain.from_iterable(izip_longest(l1, l2))` to avoid forcing the `izip_longest` iterator to be fully realized (holding a bunch of `tuple`s in memory) when it can be lazily consumed with lower overhead (no more than one such `tuple` in memory at once). You could also create a guaranteed unique sentinel value (`sentinel = object()`) and use it as the `izip_longest` `fillvalue` and `ifilter` test element (`x is not sentinel`) to remove the assumption that `None` doesn't appear. – ShadowRanger Mar 24 '18 at 00:16
  • I'll agree the optimization is largely meaningless unless the inputs are huge (millions of values sort of thing). That said, using a guaranteed unique sentinel is about reliability/correctness in all cases, not performance. Sure, if this is for a one-off solution where the inputs are guaranteed to only be `int`s, go nuts, use `None`, but if you plan to reuse the code in any way, don't make assumptions that are invalidated by perfectly reasonable inputs. – ShadowRanger Mar 24 '18 at 19:12