python - 我在线性时间内合并两个排序列表的实现 - 有什么可以改进的？

Question

来自 Google 的 Python 类:

E. Given two lists sorted in increasing order, create and return a merged
list of all the elements in sorted order. You may modify the passed in lists.
Ideally, the solution should work in "linear" time, making a single
pass of both lists.

这是我的解决方案:

def linear_merge(list1, list2):
  merged_list = []
  i = 0
  j = 0

  while True:
    if i == len(list1):
        return merged_list + list2[j:]
    if j == len(list2):
        return merged_list + list1[i:]

    if list1[i] <= list2[j]:
        merged_list.append(list1[i])
        i += 1
    else:
        merged_list.append(list2[j])
        j += 1

首先，这里用无限循环可以吗？当我完成合并列表时，我应该使用 break 关键字跳出循环，还是这里的返回值合适？

我在这里看到过类似的问题，所有解决方案看起来都与我的非常相似，即非常类似于 C。没有更多类似 python 的解决方案了吗？或者这是因为算法的性质？

Answer 1

This question比您可能需要的更详细地介绍了这一点。 ;) 选择的答案符合您的要求。如果我需要自己做这件事，我会按照 dbr 在他或她的回答中描述的方式来做(将列表加在一起，对新列表进行排序)，因为它非常简单。

编辑:

我在下面添加了一个实现。我实际上在此处的另一个答案中看到了这一点，该答案似乎已被删除。我只是希望它没有被删除，因为它有一个我没有发现的错误。 ;)

def mergeSortedLists(a, b):
    l = []
    while a and b:
        if a[0] < b[0]:
            l.append(a.pop(0))
        else:
            l.append(b.pop(0))
    return l + a + b