在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])
推荐答案
当前代码的问题是它导致临时节点的下一个 before 导航到下一个节点的副作用从当前节点.当当前临时节点是当前节点时,这是有问题的.
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屋!
查看全文