下面是我的代码:
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
这里的问题被困在无限循环中。谁能告诉我出了什么问题?
的例子是:
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])
当前代码的问题是，在从当前节点导航到下一个节点之前，它会导致临时节点的下一个的副作用。当当前临时节点是当前节点时，这是有问题的。
也就是说，想象一下这种情况:
temp = N
temp.next = N # which means N.next = N
N = N.next # but from above N = (N.next = N) -> N = N
有一个更正的版本，有一些其他的更新:
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
归并两个排序链表的递归算法
def merge_lists(h1, h2):
if h1 is None:
return h2
if h2 is None:
return h1
if (h1.value < h2.value):
h1.next = merge_lists(h1.next, h2)
return h1
else:
h2.next = merge_lists(h2.next, h1)
return h2
完整代码:-
为链表的每一个节点定义"Node"类。
class Node:
def __init__(self,data):
self.data = data
self.next = None
"linkedlist"类的定义。
class linkedlist:
def __init__(self):
self.head = None
"合并"函数的定义。
参数"ll1"one_answers"ll2"是两个链表的头。
def merge_lists(ll1, ll2):
if ll1 is None:
return ll2
if ll2 is None:
return ll1
if (ll1.data < ll2.data):
ll1.next = merge_lists(ll1.next, ll2)
return ll1
else:
ll2.next = merge_lists(ll2.next, ll1)
return ll2
将输入输入到列表中。
l1 = []
try:
l1 = list(map(int,input().strip().split()))
except EOFError:
pass
l2 = []
try:
l2 = list(map(int,input().strip().split()))
except EOFError:
pass
创建链表，即ll1和ll2。
ll1 = linkedlist()
ll1.head = Node(l1[0])
itr1 = ll1.head
for i in range(1,n1):
temp = Node(l1[i])
itr1.next = temp
itr1 = itr1.next
ll2 = linkedlist()
ll2.head = Node(l2[0])
itr2 = ll2.head
for i in range(1,n2):
temp = Node(l2[i])
itr2.next = temp
itr2 = itr2.next
使用merge函数通过传递两个链表的头来合并两个排序的链表
itr = merge(ll1.head,ll2.head)
"merge"函数返回一个迭代器本身，其值打印为:
while itr != None:
print(itr.data,end=" ")
itr = itr.next
自定义输入输出:-
输入1 41 3 5 7
42 4 6 12
输出对我来说，将LinkedList转换为list并返回更加python化。我还实现了print函数输出LinkedList，这有助于测试和调试。
def ln_to_list(ln):
tmp = ln
lst = [ln.val]
while tmp.next:
tmp = tmp.next
lst.append(tmp.val)
return lst
def print_ln(ln):
return '->'.join([str(el) for el in ln_to_list(ln)])
def ln_from_list(lst):
if not lst or len(lst) == 0:
return None
head = ListNode(lst[0])
tmp = head
for i in lst[1:]:
tmp.next = ListNode(i)
tmp = tmp.next
return head
首先让我澄清一下，这是我提到的leet代码的问题，所以这里我只是想回答这个问题，逻辑本身。
时间复杂度:O(n+m)，其中n为len(l1)， m为len(l2)，因为我们只遍历一次。
空间复杂度:0(1)，我们不创建任何新的对象，只是重新连接彼此。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1, l2):
head = res = ListNode()
while l1 and l2:
if l1.val <= l2.val:
res.next = l1
l1 = l1.next
else:
res.next = l2
l2 = l2.next
res = res.next
if l1: res.next = l1
if l2: res.next = l2
return(head.next)
#创建一个新的链接列表，用于存储结果
#这里我使用了对同一个列表的两个引用，因为我应该返回列表
的根#head将在此过程中使用，并返回res。——