萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第21题-合并两个有序链表

发表于 2022-04-19 | 分类于 力扣刷题 | 0 | 阅读次数 104

题目描述

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

样例

示例 1:
image.png
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:
输入:l1 = [], l2 = []
输出:[]

示例 3:
输入:l1 = [], l2 = [0]
输出:[0]

题目评估

官方难度:简单
知识点:链表、递归

分析

顺序写法:定义双指针,从头向后比较两指针指向的节点数值,然后根据比较结果改变链表每个节点的指向并滑动指针,顺序的比较完两个链表。
递归写法(迭代):如果一个节点为空直接返回另一个节点,如果两个节点都不空才比较两个节点的值的大小,值小的一方成为主节点连接后边的节点,即递归调用自己。

Java代码题解

顺序写法:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 只要有一个链表为空就返回另一个非空链表
        if (list1 == null && list2 != null) {
            return list2;
        }
        if (list1 != null && list2 == null) {
            return list1;
        }
        if (list1 == null && list2 == null) {
            return null;
        }
        // 定义fp和sp为两个链表的滑动指针
        ListNode fp = list1;
        ListNode sp = list2;
        // 顶一个头结点
        ListNode res = new ListNode();
        // 定义一个结果指针的滑动指针
        ListNode next = res;
        while (fp != null && sp != null) {
            // 1链表的值小就将当前节点连接在结果指针中,然后滑动指针
            if (fp.val < sp.val) {
                next.next = fp;
                fp = fp.next;
            }
            // 2链表同理1链表
            else {
                next.next = sp;
                sp = sp.next;
            }
            next = next.next;
        }
        // 处理链表中剩余节点
        if (fp != null) {
            next.next = fp;
        } else if (sp != null) {
            next.next = sp;
        }
        return res.next;
    }
}

递归写法:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

复杂度分析

时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。
递归写法空间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O(n+m)。
顺序写法(迭代)空间复杂度:O(1)。

# 算法 # 程序设计 # 力扣
力扣第20题-有效的括号
Spring注解学习[email protected]注解
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持