0基础教程习题24—合并两个有序list

1、题目要求

 

已知有两个有序的列表，内容分别为

[2,4,6,9] 和 [3,5,8,10] ，请编写一个函数，合并这两个列表并返回，合并后，列表里的元素依然是有序的

结果为[2, 3, 4, 5, 6, 8, 9, 10]

函数定义为 def merge_lst(lst1,lst2)

---

 

2、程序分析

 

1. 不要试图将一个列表的元素写入另一个列表，因为这样会破坏原来的一个列表
2. 要借助着两个列表原本就有序的特点，创建一个新的列表，然后从这两个列表里抽出数据放入新列表
3. 每次从这两个列表里取出最小的数值，进行比较，较小的那一个放入新列表
4. 重复第3步，直到其中一个列表里的元素都取走
5. 如果有一个列表里还有元素，则把剩余的元素全部放入新列表

第3步可能会让你感到一些困惑，要明白，这两个列表原本就是有序的，因此，只需要根据索引从小到大取值就可以了，你需要一个变量来记录当前这个列表已经取到元素的索引，如果这个取出来的值被放入到了新列表，这个记录索引的变量则加1，下一次取值的时候，直接使用

---

 

3、示例代码

 

#coding=utf-8

lst1 = [2,4,6,9]
lst2 = [3,5,8,10]

def merge_lst(lst1,lst2):
    lst = []
    index1,index2 = 0,0
    while index1 < len(lst1) and index2 < len(lst2):
        left = lst1[index1]
        right = lst2[index2]
        if left <= right:
            lst.append(left)
            index1 += 1
        else:
            lst.append(right)
            index2 += 1

    if index1 < len(lst1):
        lst.extend(lst1[index1:])

    if index2 < len(lst2):
        lst.extend(lst2[index2:])

    return lst

if __name__ == '__main__':
    print merge_lst(lst1,lst2)