本文讲述了python基础编程100例：第89期-基础算法：递归 合并两个有序链表！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第89期-基础算法：递归 合并两个有序链表

1 问题描述

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

示例 1:

输入: l1 = [1,2,4], l2 = [1,3,4]

输出: [1,1,2,3,4,4]

示例 2:

输入: l1 = [], l2 = []

输出: []

示例 3:

输入: l1 = [], l2 = [0]

输出: [0]

初始代码

# Definition for singly-linked list.

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

 

class LinkList:

    def __init__(self):

        self.head=None

 

    def initList(self, data):

        while len(data)==0:return None

        self.head = ListNode(data[0])

        r=self.head

        p = self.head

        for i in data[1:]:

            node = ListNode(i)

            p.next = node

            p = p.next

        return r

    def printlist(self,head):

        a=[]

        if head == None: return []

        node = head

        while node != None:

            a.append(node.val)

            node = node.next

        return a

class Solution:

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

        #在此填写代码

if __name__ == '__main__':

    print(LinkList().printlist(Solution().mergeTwoLists(LinkList().initList([1,2,4]),LinkList().initList([1,3,4]))))

    print(LinkList().printlist(Solution().mergeTwoLists(LinkList().initList([]),LinkList().initList([]))))

    print(LinkList().printlist(Solution().mergeTwoLists(LinkList().initList([]),LinkList().initList([0]))))

2 解题思路

标签：递归

终止条件：当两个链表都为空时，表示我们对链表已合并完成。

如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）

则当前位的值为(l1.val + l2.val + i) % 10

则进位值为(l1.val + l2.val + i) / 10

建立新node，然后将进位传入下一层。

3 解题方法

# Definition for singly-linked list.

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

 

class LinkList:

    def __init__(self):

        self.head=None

 

    def initList(self, data):

        while len(data)==0:return None

        self.head = ListNode(data[0])

        r=self.head

        p = self.head

        for i in data[1:]:

            node = ListNode(i)

            p.next = node

            p = p.next

        return r

    def printlist(self,head):

        a=[]

        if head == None: return []

        node = head

        while node != None:

            a.append(node.val)

            node = node.next

        return a

class Solution:

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

        import math

        if not l1 and not l2:return 

        if (l1.val if l1 else math.inf) <(l2.val if l2 else math.inf):

            node=ListNode(l1.val)

            node.next=self.mergeTwoLists(l1.next,l2)

        else:

            node=ListNode(l2.val)

            node.next=self.mergeTwoLists(l1,l2.next)

        return node

if __name__ == '__main__':

    print(LinkList().printlist(Solution().mergeTwoLists(LinkList().initList([1,2,4]),LinkList().initList([1,3,4]))))

    print(LinkList().printlist(Solution().mergeTwoLists(LinkList().initList([]),LinkList().initList([]))))

    print(LinkList().printlist(Solution().mergeTwoLists(LinkList().initList([]),LinkList().initList([0]))))

第1-30，41-44行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第31行： 引入math模块（后面会用到）

第32行： 当两个链表都遍历完时，结束函数递归

第33行： 判断l1与l2当前节点值的大小（若不存在则节点值大小为无穷大（math.inf为无穷大））

第34行： 若l1节点值小于l2节点值，则用l1节点值新建一个链表node

第35行： 链表node的下一个元素进行递归操作，内部变量分别为l1链表的后一段链表以及l2链表

第36-38行： 若l1节点值大于或等于于l2节点值，则用l2节点值新建一个链表node，并进行递归操作

第37行： 返回node链表

代码运行结果为：

算法讲解

这里用到了基础算法：递归，简单讲解下这个算法：

什么是递归

程序调用自身的编程技巧称为递归

递归做为一种算法在程序设计语言中广泛应用。

递归算法一般用于解决三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）

(2)问题解法按递归算法实现。

(3)数据的结构形式是按递归定义的。

递归函数特征

必须有一个明确的结束条件；

每次进入更深一层递归时，问题规模相比上次递归都应有所减少

相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。

递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

结构讲解

这里用到了基础结构：链表，简单讲解下这个链表：

链表

链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接

链表的结构：data为自定义的数据，next为下一个节点的地址。

基本元素

节点：每个节点有两个部分，左边称为值域，存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。

head:head节点永远指向第一个节点

tail: tail永远指向最后一个节点

None:链表中最后一个节点的指针域为None值

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。