萤火小屋

优律的知识库

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

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

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

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

题目描述

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

样例

示例 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题-有效的括号
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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