6、合并两个有序链表-Python-LeetCode-21

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

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

解法一
这题可以使用递归，判断两链表节点，指向小的节点；
（1）判断l1、l2是不是空链表，是则返回非空链表
（2）判断两节点大小，使用节点更小的链表，当前节点指向新的两链表中更小的节点，最终返回当前链表
代码如下：

# 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
        """
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

时间复杂度：O（n+m）,n和m分别是l1、l2的链表长度
空间复杂度 O（n+m），递归用到栈，每次调用都得消耗空间
奥利给！

解法二
上面递归用到栈，空间复杂度较大，咱们换一种迭代的思路；
（1）新建一个空节点prev，然后维护一个头节点用于最后链表输出，后续操作next指针即可；
（2）l1、l2都非空时，循环判断节点大小， 让空节点指向小的那个节点，并将小的节点后移一位，每次判断都将prev向后移动一位。
（3）循环结束后，l1、l2有一个为空链表，则prev得指向剩下的非空链表，保证合并链表包含l1、l2所有节点
代码如下：

# 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
        """
        prev = ListNode()
        tmp = prev
        while l1 and l2 :
            if l1.val < l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            prev = prev.next
        prev.next = l1 if l2 is None else l2
        return tmp.next
        

时间复杂度：O（n+m）
空间复杂度：O（1），操作合并链表即可
奥利给！

最后

以上就是无聊信封为你收集整理的6、合并两个有序链表-Python-LeetCode-21的全部内容，希望文章能够帮你解决6、合并两个有序链表-Python-LeetCode-21所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。