写点什么

Python 应用之基础结构 - 链表 - 合并两个有序链表

作者:向阳逐梦
  • 2022 年 10 月 08 日
    四川
  • 本文字数:2025 字

    阅读完需:约 7 分钟

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 aclass 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. 解题的思路


  • 标签:链表

  • 保存头指针,移动当前指针,比较大小,最后将还没遍历完的直接接上

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 aclass Solution:    def mergeTwoLists(self,l1: ListNode, l2: ListNode) -> ListNode:        p=ListNode(0)        q=p        while l1 and l2:            if l1.val>=l2.val:                p.next=l2                l2=l2.next            else:                p.next=l1                l1=l1.next            p=p.next        p.next = l1 if l1 is not None else l2        return q.next
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,44-47 行: 题目中已经给出的信息,运行代码时要根据这些代码进行编辑(具体为创建链表以及列表、链表转换)

第 31 行: 创建初始链表 p,头指针数值为 0

第 32 行: 保存头指针于变量 q 上,移动的是 p 指针

第 33 行: 当 l1 和 l2 都不为 None 时,循环(print(None)的结果为 False)

第 34 行: 判断 l1 当前节点的数值是否大于 l2 当前节点的数值

第 35 行: 若 l1 当前节点的数值大于 l2 当前节点的数值,则将 p 链表指向 l2

第 36 行: l2 节点指向其下一个节点

第 37-38 行: l1 当前节点的数值小于 l2 当前节点的数值,则将 p 链表指向 l1

第 39 行: l1 节点指向其下一个节点

第 40 行: p 节点指向他的下一个节点,用于为下一个节点赋值

第 41 行: 若 l1 或 l2 有一者为 None 时,代表一个链表已经遍历到结尾了,但是另一个链表还有数值,此时将 p 节点指向非空的链表

第 42 行: 返回 q.next(q.next 指向新链表的头指针)

代码运行结果为:



4. 结构讲解

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

链表

链表是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接链表的结构:data 为自定义的数据,next 为下一个节点的地址。

基本元素

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

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

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

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


发布于: 刚刚阅读数: 4
用户头像

向阳逐梦

关注

人生享受编程,编程造就人生! 2022.06.01 加入

InfoQ签约作者、阿里云“乘风者计划”签约博主

评论

发布
暂无评论
Python应用之基础结构-链表-合并两个有序链表_链表_向阳逐梦_InfoQ写作社区