函数只输出最后一个节点，不输出合并列表+链表

Question

这是我合并两个链表的方法:

def merge(self, l1, l2):
cur = Node() #Creating a dummy node
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
#Skipped a block here to keep it short, not related to the question
return cur.next

但是函数只返回最后一个节点，而不是合并，当我向它添加一个指针时，它做正确的事情:

def merge(self, l1, l2):
cur = Node() #Creating a dummy node
p = cur #Pointer
while l1 and l2:
if l1.val <= l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
return cur.next

谁能解释一下?我似乎不能理解在这里使用指针的目的。很多谢谢!

Answer 1

两个merge都不正确，它们提取元素直到它们都有元素，如果l1或l2完成它们，剩下的元素将是unmerged。

在下面的方法中，当我们返回curr时，我们只是在cur.next周围移动。接下来，它将是最后一个节点，因为我们只通过cur.next = l1或cur.next = l2设置该值，因此下面的方法将只获得最后一个Node。

while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
#Skipped a block here to keep it short, not related to the question
return cur.next

<标题>合并:

def merge(l1, l2):
start = None
curr = None
arr = list()

while l1 or l2:
if l1:
arr.append(l1.val)
l1 = l1.next
elif l2:
arr.append(l2.val)
l2 = l2.next
arr = sorted(arr)
for val in arr:
if curr:
curr.next = Node(val = val)
curr = curr.next
else:
curr = Node(val = val)
start = curr
return start 

<标题>来源:

class Node:
def __init__(self, val = None, nextN = None):
self.next = nextN
self.val = val 
def merge(l1, l2):
start = None
curr = None
arr = list()
while l1 or l2:
if l1:
arr.append(l1.val)
l1 = l1.next
elif l2:
arr.append(l2.val)
l2 = l2.next
arr = sorted(arr)
for val in arr:
if curr:
curr.next = Node(val = val)
curr = curr.next
else:
curr = Node(val = val)
start = curr
return start 
def printLink(node):
temp = node
while temp!= None :
print(temp.val, end = '-')
temp = temp.next
print()

node1 = Node(val = 1)
node1.next = Node(val = 3)
node2 = node1.next
node2.next = Node(val = 4)

node2 = Node(val = 1)
node2.next = Node(val = 3)
node3 = node2.next
node3.next = Node(val = 8)
node3.next.next = Node(val = 5)
printLink(node1)
printLink(node2)
printLink(merge(node1, node2))

Answer 2

这两个代码片段的问题是，在循环中，您将节点(l1或l2)一次又一次地附加到相同的next属性。因此，每次迭代都覆盖由前一次迭代确定的属性值。

在每次迭代中，您需要将引用移动到下一个节点——刚刚分配给next的节点。

第二个代码段稍微好一点，因为它预见到需要两个引用:一个保持在虚拟节点上，另一个在节点被分配给next属性时向前移动。

其他备注:

• 使用更多缩进。通常的做法是每个缩进使用4个空格。
• 使用描述性变量名。如果节点是虚拟节点，为什么不调用它dummy?

:

def merge(self, l1, l2):
dummy = Node()
current = dummy

while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next  # This was missing!
# Attach the remainder (either l1 or l2)
current.next = l1 or l2
return dummy.next