剑指offer25:合并两个排序的链表 python_华为软通题输入两个递增的链表链表长度为n python 空间复杂度

题目描述

解法

1. 双指针法，一个指针指向第一个链表，一个指针指向另一个链表

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dump1 = ListNode(0) #引入伪节点
        dump = dump1
        while l1 and l2:  #两个链表中一个为空的时候退出循环
            if l1.val <= l2.val:
                dump.next = l1
                dump = dump.next
                l1 = l1.next
            else:
                dump.next = l2
                dump = dump.next
                l2 = l2.next
        if l1 is None:  #把另一个不为空的链表接上去
            dump.next = l2
        if l2 is None:
            dump.next = l1
        return dump1.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度O(M+N)，空间复杂度O(M+N)（构建了新的链表）

递归法

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> 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
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2
1
2
3
4
5
6
7
8
9
10
11

时间复杂度O(M+N)，空间复杂度O(1)，因为没有构建新的列表

思考感想