题目描述

[EN | CN]

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

示例:

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

解法 1:直接法

按照题意直接拼就好了。

假设两个链表长度分别为 $m$、$n$,那么

  • 时间复杂度为 $O(m + n)$,比较次数;
  • 空间复杂度为 $O(1)$,直接 inplace 修改,不需要额外空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        curr = head
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next, l1 = l1, l1.next
            else:
                curr.next, l2 = l2, l2.next
            curr = curr.next
        if l1:
            curr.next = l1
        if l2:
            curr.next = l2
        return head.next
  • 执行用时:48 ms,在所有 Python3 提交中击败了 51.09% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 7.14% 的用户。