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

Question

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

我对链表不是很有经验，但我正在尝试解决更多问题以获得曝光。我的代码只返回 [4]，而不是返回 [1,1,2,3,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