如何在给定两个已排序列表的情况下创建已排序列表（不能修改任一给定列表）

Question

我的目标是创建一个函数，将两个排序的int列表作为参数 并创建已排序的合并列表。唯一的问题是我不被允许 修改两个原始列表（并且不能复制以修改其中一个）。只有range（）、len（）、index（）、append（）是允许的内置项。到目前为止，我被难住了。你知道吗

以下是我所拥有的：

def merge_lists( list1, list2 ):

sortedList = []

pointer1 = 0

pointer2 = 0

while pointer1 < len( list1 ) and pointer2 < len( list2 ):

    if list1[ pointer1 ] < list2[ pointer2 ]:

        sortedList.append( list1[ pointer1 ] )

        pointer1 += 1

    elif list2[ pointer2 ] < list1[ pointer1 ]:

        sortedList.append( list2[ pointer2 ] )

        pointer2 += 1

    elif list1[ pointer1 ] == list2[ pointer2 ]:

        sortedList.append( list1[ pointer1 ] )

        sortedList.append( list2[ pointer2 ] )

        pointer1 += 1

        pointer2 += 1

if pointer1 == 0:

    for number in list1:

        sortedList.append( number )

if pointer2 == 0:

    for number in list2:

        sortedList.append( number )

else:

    amountNumbersLeft1 = len( list1 ) - ( pointer1 - 1 )

    amountNumbersLeft2 = len( list2 ) - ( pointer2 - 1 )

    if amountNumbersLeft1 != 0:

        for o in range( 1, ( amountNumbersLeft1 ) ):

            sortedList.append( list1[ o ] )

    if amountNumbersLeft2 != 0:

        for i in range( 1, ( amountNumbersLeft2 ) ):

            sortedList.append( list2[ i ] )

return sortedList

我的测试用例以（[1，2，3]，[4，5，6]）作为参数，返回一个列表[1，2，3，4，5，6]。但是，我的测试用例（[2，13，19]，[3，6，9，22]）返回了[2，3，6，9，13，19，6]。你知道吗

我觉得有一个更简单的排序解决方案。请帮忙。谢谢。你知道吗

Answer 1

这很简单。使用+合并列表，然后使用排序函数。你知道吗

merged = sorted(list1 + list2)

Answer 2

代码实际上比你写的要简单得多。你知道吗

def merge_lists(list1, list2):
    sortedList = []
    pointer1 = 0
    pointer2 = 0

    while pointer1 < len(list1) and pointer2 < len(list2):
        if list1[pointer1] < list2[pointer2]:
            sortedList.append(list1[pointer1])
            pointer1 += 1
        elif list1[pointer1] > list2[pointer2]:
            sortedList.append(list2[pointer2])
            pointer2 += 1
        else:
            sortedList.append(list1[pointer1])
            pointer1 += 1

    while pointer1 < len(list1):
        sortedList.append(list1[pointer1])
        pointer1 += 1

    while pointer2 < len(list2):
        sortedList.append(list2[pointer2])
        pointer2 += 1

    return sortedList

代码中的问题是pointer1和pointer2永远不会为0，因为它们是递增的。因此，您总是执行pointer2 == 0条件的else分支。else语句中的逻辑是错误的，因为您再次从索引1添加数字，如for循环中所述。这就是为什么要再次添加6而不是22，它是示例中第二个列表的索引1处的值。你知道吗

Answer 3

您的for循环在两个列表上迭代并不断追加较小的值并递增相应的索引是正确的。你知道吗

   def merge_lists( list1, list2 ):

       sortedList = []
       pointer1 = 0
       pointer2 = 0

       while pointer1 < len( list1 ) and pointer2 < len( list2 ):
           if list1[ pointer1 ] < list2[ pointer2 ]:
               sortedList.append( list1[ pointer1 ] )
               pointer1 += 1
           elif list2[ pointer2 ] < list1[ pointer1 ]:
               sortedList.append( list2[ pointer2 ] )
               pointer2 += 1
           elif list1[ pointer1 ] == list2[ pointer2 ]:
               sortedList.append( list1[ pointer1 ] )
               sortedList.append( list2[ pointer2 ] )
               pointer1 += 1
               pointer2 += 1

到目前为止一切都很好。错误发生在之后。在这个时候，至少有一个名单已经用尽了。因此，只需运行2for循环，就可以将未用尽列表中的剩余数字相加。你知道吗

   while pointer1 < len( list1 ):
       sortedList.append( list1[ pointer1 ] )
       pointer1 += 1

   while pointer2 < len( list2 ):
       sortedList.append( list2[ pointer2 ] )
       pointer2 += 1

   return sortedList

简单明了：）