合并两个有序列表

python 算法

合并两个有序列表，刚看到这个题时，脑子里冒出的就是归并排序。应该比归并排序还要简单。下面就撸撸代码！

# coding= utf-8
def merge_two_order_list(seq1, seq2):
    rst = []
    while len(seq1) > 0 and len(seq2) > 0:
        if seq1[-1] > seq2[-1]:
            rst.append(seq1.pop())
        else:
            rst.append(seq2.pop())
    rst.extend(list(reversed(seq1)))
    rst.extend(list(reversed(seq2)))
    rst.reverse()
    return rst

还有递归版本

# coding= utf-8
def merge_two_list_recursion(seq1, seq2, rst=None):
    if rst is None:
        rst = []
    if len(seq1) == 0 or len(seq2) == 0:
        rst.extend(list(reversed(seq1)))
        rst.extend(list(reversed(seq2)))
        return rst
    if seq1[-1] > seq2[-1]:
        rst.append(seq1.pop())
    else:
        rst.append(seq2.pop())
    return merge_two_list_recursion(l1, l2, rst)