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

Python是一门需要不断实践练习的编程语言,本文档将AI大学堂学员交流群的Python每周练习进行汇总,希望各位小伙伴能够多进行实践练习,逐渐爱上这门神奇的编程语言,掌握它并在生活中能够使用它。

# 1 问题描述

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

示例 1:

image.jpg
输入: 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]))))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

第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链表

代码运行结果为:
image.jpg

# 算法讲解

这里用到了基础算法:递归,简单讲解下这个算法:
什么是递归
程序调用自身的编程技巧称为递归
递归做为一种算法在程序设计语言中广泛应用。


递归算法一般用于解决三类问题:
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。
(3)数据的结构形式是按递归定义的。


递归函数特征
必须有一个明确的结束条件;
每次进入更深一层递归时,问题规模相比上次递归都应有所减少
相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)。
递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出)

# 结构讲解

这里用到了基础结构:链表,简单讲解下这个链表:
链表
链表是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接
链表的结构:data为自定义的数据,next为下一个节点的地址。
image.jpg
基本元素
节点:每个节点有两个部分,左边称为值域,存放用户数据;右边部分称为指针域,用来存放指向下一个元素的指针。
head:head节点永远指向第一个节点
tail: tail永远指向最后一个节点
None:链表中最后一个节点的指针域为None值

# 4 视频解析

高清视频讲解,请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号,发送 python100 即可领取Python基础实战100例源代码
AI大学堂公众号.png

更新于: 12/28/2021, 7:43:14 AM