python - 如何在线性时间内合并Python中的两个排序列表(仅遍历一次)？

Question

这个问题已经有答案了:

Combining two sorted lists in Python (22 个回答)

已关闭 5 年前。

list_a = [1,7,9,35,36,37]
list_b = [3,4,5,40]

预期输出:

list_merged = [1,3,4,5,7,9,35,36,37,40]

条件:必须只遍历两个列表一次

我知道zip其工作原理如下，非常符合我的要求。

>>> x = [1, 2]
>>> y = [1, 3, 4, 5, 6]
>>> zip(x,y)
[(1, 1), (2, 3)]
>>> zip(y, x)
[(1, 1), (3, 2)]

Answer 1

这是我自己尝试过的。解决方案并不短，但是简单..

def linear_merge(list1, list2):
  i = 0
  j = 0
  list_m = [] # resultant list

  while i < len(list1) and j < len(list2):
    if list1[i] <= list2[j]: #take element from list 1 
      list_m.append(list1[i])
      i += 1
    else: # or take element from list 2
      list_m.append(list2[j])
      j += 1

  if i <= len(list1) - 1: #append remaing elements from list 1 
    list_m.extend(list1[i:])
  elif j <= len(list2) - 1: #or append remaing elements from list 2
    list_m.extend(list2[j:])

  return list_m

对我来说，这在第一手资料中是有效的，似乎是 C 方式。还有更多pythonic解决方案吗？