在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
这里的问题是陷入了无限循环。谁能告诉我问题出在哪里？
以下是一些例子：
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])
5 个回答
0
首先我想说明一下，这个问题是出在LeetCode上，正如我提到的，我只是想解答这个问题的逻辑。
时间复杂度：O(n+m)，这里的n是l1的长度，m是l2的长度，因为我们只遍历了一次。
空间复杂度：O(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会被返回。
0
在我看来，把链表转成列表再转回来更符合Python的风格。我还实现了一个打印函数，用来输出链表的内容，这样在测试和调试的时候会更方便。
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
0
完整代码：
这是“Node”类的定义，用于表示链表中的每一个节点。
class Node:
def __init__(self,data):
self.data = data
self.next = None
这是“linkedlist”类的定义。
class linkedlist:
def __init__(self):
self.head = None
这是“Merge”函数的定义。
参数“ll1”和“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
通过传入两个链表的头节点，使用合并函数将两个已排序的链表合并。
itr = merge(ll1.head,ll2.head)
“merge”函数返回一个迭代器，里面的值会被打印出来，格式如下：
while itr != None:
print(itr.data,end=" ")
itr = itr.next
自定义输入和输出：
输入：
1
4
1 3 5 7
4
2 4 6 12
输出：
1 2 3 4 5 6 7 12
11
合并两个已排序链表的递归算法
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
16
当前代码的问题在于，它在从当前节点移动到下一个节点之前，先改变了临时节点的下一个指针。这在临时节点就是当前节点的时候，会导致问题。
换句话说，想象一下这种情况：
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