python算法--合并两个有序链表_Python

python算法--合并两个有序链表

1、比较直观的方式

用两个分别指向两个链表的指针，一起滑动.

(1)用一个指针head始终跟踪当前最新的节点，也就是最终的有序链表list的最后一个元素

（2）另外l1和l2分别向后滑动进行值得比较，每一轮的比较都会将比较中的更小的那个值加入到结果链表中(结果链表通过head串联起来)

（3）因为每一轮比较只加入一个值，所以最终只有最后一轮比较的其中一个节点没有添加进来

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

        static_head = ListNode(0)
        head = static_head
        while l1 and l2:
            if l1.val <= l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next

            head = head.next

        if l1:
            head.next = l1
        else:
            head.next = l2

        return static_head.next

2、递归的方法

# -*- coding: utf-8 -*-
"""
@File  : recursion_merge_two_lists.py
@Author: zhang_san
@Time  : 2020/8/27 09:38
@des   : 使用递归的方式完成两个链表的合并，其实合并有序链表的过程，就是不断的从两个链表中找出最小值的过程，所以这是
         一个不断的循环调用自身的过程。可以看作是，已经找出的最小值不断的与剩下的操作连接的过程，因为每一次操作都会
         找一个最下值。所以，思路如下：
         （1）根据题意，被调用的循环体，就是每次找出最小值，与剩余的有序链表连接，这里找出剩余的有效链表的过程就是一
             个循环体，因为它也是由一个最小值和有序链表形成的。
         （2）对于什么时候停止，只有当一个为空了，那么自然就不用比较了，直接返回另一个有序链表即可
"""
from linked_list import ListNode, generateList, printList

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 停止条件
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        # 在当前步需要做的事，其实就是对当前元素的操作，我们知道，当前的就是最新需要比较的l1 和l2指定的两个元素，
        # 决定哪个元素更小，然后这个元素就与剩下的循环体相连接
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

l1 = generateList([1, 2, 4])
l2 = generateList([1, 3, 4])
s = Solution()
printList(s.mergeTwoLists(l1, l2))

本文地址：https://blog.csdn.net/u011412768/article/details/108249904