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

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

您的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

简单明了：）