21. 合并两个有序链表 [easy]

21. 合并两个有序链表 [easy]

https://leetcode-cn.com/problems/merge-two-sorted-lists/

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

通过次数305,417 | 提交次数483,381

Second Try

2020-07-07

递归写法，理解起来也非常简单, 看题解了解的思路，不错

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2 
        if not l2:
            return l1 
        
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1 
        else:
            l2.next = self.mergeTwoLists(l2.next, l1)
            return l2 
        

• 执行用时：44 ms, 在所有 Python 提交中击败了5.40%的用户
• 内存消耗：12.9 MB, 在所有 Python 提交中击败了10.00%的用户

First Try

2020-07-06

搞个dummy node在开头挺好的，思路清晰了许多。

遇到链表问题，就习惯写个while。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        empty = nnode = ListNode(None)
        while l1 and l2:
            if l1.val <= l2.val:
                nnode.next = l1
                nnode = nnode.next
                l1 = l1.next
            else:
                nnode.next = l2
                nnode = nnode.next
                l2 = l2.next

        if l1:
            nnode.next = l1
        if l2:
            nnode.next = l2

        return empty.next

• 执行用时：20 ms, 在所有 Python 提交中击败了95.83%的用户
• 内存消耗：12.7 MB, 在所有 Python 提交中击败了10.00%的用户