如何在Python中合并两个已排序链表

Question

我尝试了很多算法来合并链表……

def merge_lists(head1,head2):
    if head1 is None and head2 is None:
        return None
    elif head1 is None:
        return head2
    elif head2 is None:
        return head1
    if head1.value <= head2.value:
        result = head1
    else:
        result = head2
    while head1 != None or head2 != None:
        if head1 != None and head2 != None:
            if head1.value <= head2.value:
                result.next = head1
                head1 = head1.next
            else:
                result.next = head2
                head2 = head2.next
        elif(head1!=None):
            result.next = head1
        elif(head2!=None):
            result.next = head2
    return result
    pass

比如，这些是测试用例

assert [] == merge_lists([],[])
assert [1,2,3] == merge_lists([1,2,3], [])
assert [1,2,3] == merge_lists([], [1,2,3])
assert [1,1,2,2,3,3,4,5] == merge_lists([1,2,3], [1,2,3,4,5])
assert [1,10] == merge_lists([10], [1])
assert [1,2,4,5,6,7] == merge_lists([1,2,5], [4,6,7])

有没有人能给我一段代码，让我能通过这些测试用例？提前谢谢大家。

Answer 1

def merge_lists(x,y):
    comb = []
    comb += x + y
    comb.sort()
    return comb

当然可以！请把你想要翻译的内容发给我，我会帮你把它变得简单易懂。

Answer 2

这个操作实际上是在进行一种叫做“归并排序”的“合并”步骤，所需的时间是 O(l1+l2)。

基本的思路是同时遍历两个已经排好序的列表，但只推进值较小的那个列表，同时把这个值放到结果中。这个操作会一直进行，直到两个源列表都被遍历完。

这里有一些来自维基百科的 伪代码，将其转换成链表的数据类型应该不会太难。当你为链表实现这个功能时，可以选择创建一个新列表，或者直接修改其中一个列表。

function merge(left, right)
    // receive the left and right sublist as arguments.
    // 'result' variable for the merged result of two sublists.
    var list result
    // assign the element of the sublists to 'result' variable until there is no element to merge. 
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
           // compare the first two element, which is the small one, of each two sublists.
            if first(left) <= first(right)
                // the small element is copied to 'result' variable.
                // delete the copied one(a first element) in the sublist.
                append first(left) to result
                left = rest(left)
            else
                // same operation as the above(in the right sublist).
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            // copy all of remaining elements from the sublist to 'result' variable, 
            // when there is no more element to compare with.
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            // same operation as the above(in the right sublist).
            append first(right) to result
            right = rest(right)
    end while
    // return the result of the merged sublists(or completed one, finally).
    // the length of the left and right sublists will grow bigger and bigger, after the next call of this function.
    return result