在 Python 中合并两个排序的链表

Question

我正在解决一个Leetcode问题(问题#21(，该问题需要两个排序的链表并返回一个排序的合并链表。例如，输入：1->2->4、1->3->4 和输出：1->1->2->3->4->4。

我对链表不是很有经验，但正在尝试解决更多问题以获得曝光。我的代码没有返回所需的输出 [1,1,2,3,4,4]，而是只返回 [4]。但是，我认为主要逻辑就在那里，我希望错过一些小东西。

def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
newList = ListNode(0) # used for single, merged list
while l1 and l2:
if l1.val <= l2.val: # compare current node's values
newList.next = l1
l1 = l1.next
else:
newList.next = l2
l2 = l2.next
return newList.next # first node is 0, which we don't want

Answer 1

主逻辑几乎就在那里，但您每次只替换列表中的下一项(您没有前进列表(，因此您只返回最后一项。解决方案是创建另一个"cur指针"来推进列表，同时将 newList 保留为返回结果的"前端指针"。

同样在最后，您应该与非空列表"连接">

def mergeTwoLists(self, l1, l2):
newList = ListNode(0)
cur = newList 
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2 # add non-empty list
return newList.next