我尝试了很多算法来合并链表...
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])
谁能给我代码通过这些测试用例？提前致谢。
此操作只是在执行“合并排序”的“合并”步骤，可以及时完成O(l1+l2)。
一般前提是同时遍历两个（已排序的）列表，但仅以最低头值推进列表，而在结果输出中使用高级值。当两个源列表都用尽时，该操作完成。
这是一些伪代码（由Wikipedia提供），对于链表数据类型而言，翻译起来应该不会太难。为链表实现它时，可以创建一个新列表，也可以破坏性地修改其中一个列表。
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
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句