将两个排序的链表合并为python中的一个链表 [英] merging two sorted linked lists into one linked list in python
本文介绍了将两个排序的链表合并为python中的一个链表的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
这是我的代码:
def merge_lists(head1, head2):
if head1 is None and head2 is None:
return None
if head1 is None:
return head2
if head2 is None:
return head1
if head1.value < head2.value:
temp = head1
else:
temp = head2
while head1 != None and head2 != None:
if head1.value < head2.value:
temp.next = head1
head1 = head1.next
else:
temp.next = head2
head2 = head2.next
if head1 is None:
temp.next = head2
else:
temp.next = head1
return temp
pass
这里的问题陷入了无限循环.任何人都可以告诉我问题是什么
the problem here is stucked in the infinite loop.can any one tell me what the problem is
示例为:
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])
推荐答案
当前代码的问题是,它会导致临时节点的下一个之前的副作用,后者会导航到下一个节点从当前节点开始.当当前临时节点是当前节点时,这是有问题的.
The problem with the current code is that it causes a side-effect of the temp node's next before it navigates to the next node from the current node. This is problematic when the current temp node is the current node.
也就是说,想象一下这种情况:
That is, imagine this case:
temp = N
temp.next = N # which means N.next = N
N = N.next # but from above N = (N.next = N) -> N = N
存在一个已更正的版本,并进行了其他一些更新:
There is a corrected version, with some other updates:
def merge_lists(head1, head2):
if head1 is None:
return head2
if head2 is None:
return head1
# create dummy node to avoid additional checks in loop
s = t = node()
while not (head1 is None or head2 is None):
if head1.value < head2.value:
# remember current low-node
c = head1
# follow ->next
head1 = head1.next
else:
# remember current low-node
c = head2
# follow ->next
head2 = head2.next
# only mutate the node AFTER we have followed ->next
t.next = c
# and make sure we also advance the temp
t = t.next
t.next = head1 or head2
# return tail of dummy node
return s.next
这篇关于将两个排序的链表合并为python中的一个链表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文