在 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