【算法训练-链表 零】链表高频算法题看这一篇就够了

一轮的算法训练完成后,对相关的题目有了一个初步理解了,接下来进行专题训练,以下这些题目就是汇总的高频题目
在这里插入图片描述

题目题干直接给出对应博客链接,这里只给出简单思路、代码实现、复杂度分析

反转链表

依据难度等级分别为反转链表、区间反转链表、K个一组反转链表,【算法训练-链表 一】【反转链表】反转链表、区间反转链表、K个一组反转链表

反转链表【EASY】

LeetCode地址,双指针移动逐个扭转指针方向,关键词:双指针,临时节点
在这里插入图片描述


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 1 入参校验,如果链表为空或者只有一个节点,直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 2 定义双指针节点进行遍历反转操作
        ListNode pre = null;
        ListNode cur = head;

        // 3 遍历链表,进行反转操作
        while (cur!= null) {
            // 1 定义临时节点存储当前节点的下一个节点
            ListNode pNext = cur.next;
            // 2 当前节点断开指向上一个节点
            cur.next = pre;
            // 3 双指针向前移动
            pre = cur;
            cur = pNext;
        }

        // 4 返回尾节点,也就是新的头节点
        return pre;
    }
}

时间复杂度:O(N),遍历了一遍链表
空间复杂度:O(1), 额外使用了常数级的指针变量

区间反转链表【MID】

LeetCode地址,双指针到指定位置就位,然后进行区间内的反转操作,关键词:双指针,临时节点,虚拟头节点
在这里插入图片描述


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 1 入参校验,如果链表为空或者只有一个节点,直接返回
        if (head == null || head.next == null) {
            return head;
        }
        // 如果整数left和right相等或者left大于right,直接返回
        if (left == right || left > right) {
            return head;
        }

        // 2 定义虚拟头节点与双指针,如果头节点也被反转了就丢了,所以需要虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode cur = head;

        // 3 双指针同时向前left-1步走到修改位置
        for (int i = 1; i < left; i++) {
            cur = cur.next;
            pre = pre.next;
        }

        // 4 双指针开始在区间内进行反转操作1-2-3-4-5
        for (int i = left; i < right; i++) {
            // 记录节点3
            ListNode pNext = cur.next;
            // 节点2指向节点4
            cur.next = pNext.next;
            // 节点3指向节点2
            pNext.next = pre.next;
            // 节点1指向节点3 : 1-3-2-4-5, cur一直指向节点2,pre一直指向节点1,下一轮4和3-2整体交换
            pre.next = pNext;
        }

        // 5 返回区间反转后的链表
        return dummyHead.next;
    }
}

时间复杂度:O(N),遍历了一遍链表
空间复杂度:O(1), 额外使用了常数级的指针变量

K个一组反转链表【HARD】

LeetCode地址,递归的将区间进行反转然后进行拼接,关键词:双指针,递归
在这里插入图片描述


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1 入参校验,如果链表为空或者只有一个节点或者k小于2,直接返回
        if (head == null || head.next == null || k < 2) {
            return head;
        }

        // 2 设置区间尾节点等于头节点
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            // 如果tail为空,说明链表长度小于k,无需反转,直接返回这段子区间的头节点
            if (tail == null) {
                return head;
            }
            // 如果tail不为空,tail指针向前移动,移动k步,直到移动到下一区间头节点
            tail = tail.next;
        }

        // 3 对区间进行反转操作,返回新的头节点
        ListNode newHead = reverse(head, tail);

        // 4 反转后,head变成了当前区间尾节点,tail作为下一子区间头节点传入方法递归,区间连接
        head.next = reverseKGroup(tail, k);

        // 5 返回新的头节点
        return newHead;
    }

    // 区间反转链表
    private ListNode reverse(ListNode head, ListNode tail) {
        // 1 入参判断,如果链表为空或者只有一个节点,直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 2 定义双指针节点进行遍历反转操作
        ListNode pre = null;
        ListNode cur = head;

        // 3 遍历链表,进行反转操作,tail为下一区间的头节点,所以这里是cur != tail
        while (cur != tail) {
            // 记录当前节点的下一个节点
            ListNode pNext = cur.next;
            // 当前节点断开指向上一个节点
            cur.next = pre;
            // 双指针向前移动
            pre = cur;
            cur = pNext;
        }

        // 4 返回尾节点,也就是新的头节点
        return pre;
    }
}

时间复杂度:O(N),虽然递归反转,但链表只遍历了一遍
空间复杂度:O(N/K)*O(1),递归的最大栈深度,也就是递归深度 *每次递归的空间复杂度

合并链表

依据难度分为合并两个有序链表以及合并K个有序链表,【算法训练-链表 二】【合并链表】合并两个有序链表、合并K个有序链表

合并两个有序链表【EASY】

LeetCode地址,主要思路就是双指针在两个有序链表上漫游,将较小的依次补全到新的链表上,关键词:双指针
在这里插入图片描述


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1 入参校验,如果链表为空直接返回
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        // 2 定义虚拟头节点和两个漫游指针
        ListNode dummyHead = new ListNode(-1);
        ListNode p1 = list1;
        ListNode p2 = list2;
        ListNode p = dummyHead;

        // 3 双指针分别在两个链表漫游
        while (p1 != null && p2 != null) {
            // 1 下一个节点挂p1
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                // 2 下一个节点挂p2
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        // 4 如果其中一个链表空了则挂另一个链表
        if (p1 == null) {
            p.next = p2;
        }
        if (p2 == null) {
            p.next = p1;
        }

        // 5 返回头结点
        return dummyHead.next;
    }
}

时间复杂度:O(N+M),分别对两个链表进行了遍历
空间复杂度:O(1), 额外使用了常数级的指针变量

合并K个有序链表【HARD】

LeetCode地址,应用分治的思想,先将K个有序链表进行划分,然后两两合并,关键词:双指针,分治
在这里插入图片描述
划分完子问题,子问题处理完返回到上一层级
在这里插入图片描述


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return divideMerge(lists, 0, lists.length-1);
    }

    // 划分子问题
    private ListNode divideMerge(ListNode[] lists, int left, int right) {
        // 1 终止条件,划分到最后的单个链表
        if (left > right) {
            return null;
        }
        // 2 划分到最小单个链表直接返回
        if (left == right) {
            return lists[left];
        }
        // 3 合并两个链表
        int mid = left + (right - left) / 2;
        return mergeTwoLists(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }

    // 合并两个有序链表
    private ListNode mergeTwoLists(ListNode pHead1, ListNode pHead2) {
        // 1 入参校验,如果链表为空直接返回
        if (pHead1 == null && pHead2 == null) {
            return null;
        }
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }

        // 2 定义虚拟头节点和两个漫游指针
        ListNode dummyHead = new ListNode(-1);
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        ListNode cur = dummyHead;

        // 3 双指针分别在两个链表漫游
        while (p1 != null && p2 != null) {
            // 1 下一个节点挂p1
            if (p1.val <= p2.val) {
                cur.next = p1;
                p1 = p1.next;
            } else {
                // 2 下一个节点挂p2
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }

        // 4 如果其中一个链表空了则挂另一个链表
        if (p1 == null) {
            cur.next = p2;
        }
        if (p2 == null) {
            cur.next = p1;
        }

        // 5 返回头结点
        return dummyHead.next;
    }
}

时间复杂度:O(NLogN),二分分治进行了LogN次划分,每次遍历时间复杂度为O(N)
空间复杂度:O(LogN), 递归栈深度为LogN

链表查找

依据难度为:查找链表中倒数第K个节点,【算法训练-链表 六】【链表查找】:链表中倒数第k个节点

链表中倒数第k个节点【EASY】

LeetCode地址,解题思路就是应用快慢指针,快指针先于慢指针K步,然后同时移动,这样快指针到达链表尾部,慢指针刚好在倒数第K个节点,关键词:快慢指针


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        // 1 入参校验如果head为空或者cnt小于1,返回head
        if (head == null || head.next == null || cnt < 1) {
            return head;
        }

        // 2 定义快慢指针都指向头结点
        ListNode fast = head;
        ListNode slow = head;

        // 3 快指针先前进cnt步
        for (int i = 1; i < cnt; i++) {
            // fast为null,证明给的用例cnt大于链表总长度,返回null
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }

        // 4 快慢指针同时前进,当快指针为尾节点时,慢指针位置就是倒数第K个
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 5 返回slow的位置
        return slow;
    }
}

时间复杂度:O(N),遍历了一遍链表
空间复杂度:O(1), 额外使用了常数级的指针变量

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/142736.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Window安装MongoDB

三种NOSQL的一种,Redis MongoDB ES 应用场景: 1.社交场景:使用Mongodb存储用户信息,以及用户发表的朋友圈信息,通过地理位置索引实现附近的人,地点等功能 2.游戏场景:使用Mongodb存储游戏用户信息,用户的装备,积分等直接以内嵌文档的形式存储,方便查询,高效率存储和访问…

Python 如何实现访问者设计模式?什么是访问者(Visitor)模式?实际案例中有什么作用?

什么是访问者设计模式&#xff1f;访问者&#xff08;Visitor&#xff09;设计模式介绍&#xff1a; 访问者&#xff08;Visitor&#xff09;设计模式是一种行为设计模式&#xff0c;用于在不修改被访问对象的前提下定义新的操作。它通过将操作封装到独立的访问者类中&#xf…

JumpServer管理虚拟机

环境准备 1.虚拟机192.168.1.111在线安装JumpServer https://blog.csdn.net/tongxin_tongmeng/article/details/1340166222.虚拟机192.168.1.112创建用户changwq、wangwj useradd changwq && passwd changwq、useradd wangwj && passwd wangwj3.虚拟机192.168.…

springboot容器

1.主要指的是servlet容器 servlet组件由sevlet Filter Listener等 2.自动配置原理 通过ServletWebServerFactoryAutoConfiguration 配置这些内容 (自动配置类开始分析功能) conditionalOnclass开启条件 ServletRequest类 import导入嵌入式的tomcat Jetty等 这些是配置类&…

本地化工具:Soluling Localization Crack

Soluling 是一个本地化工具&#xff0c;包含本地化项目所需的所有功能。Solling 使本地化变得非常容易。Soluling 是桌面应用程序和命令行工具的组合 。Solling支持100多种文件格式。通过 Soluling&#xff0c;您可以本地化桌面应用程序、移动应用程序、Web 应用程序、文档和在…

如何在thingsboard的规则链中对一个遥测属性进行求平均值

背景 有这样一个需求,一个温度传感器每5秒,上传一次数据。要求算出该设备2分钟内的平均温度,如果超过某个值,则发送告警邮件。 具体操作实现 下面在规则链中实现求平均值。 使用的节点是 配置如下 必填 Timeseries keys,是要求的平均值的属性名。 我这里求的是四个…

【教学类-17-03】20231105《世界杯随机参考图七巧板 3份一页》(大班)

效果展示&#xff1a; 单页效果 多页效果 预设样式&#xff1a; 背景需求&#xff1a; 2022年11月24日&#xff0c;大1班随机抽取的9位幼儿制作了9张拼图&#xff0c;发现以下三个问题&#xff1a; 1、粉红色辅助纸选择量多——9份作业有4位幼儿的七巧板人物是粉红色的 2、…

嵌入式杂记 -- MCU的大小端模式

MCU的大小端模式 大端模式小端模式大小端模式测试联合体概念MCU大小端模式测试大端模式测试小端模式测试 大小端模式转换 在进行MCU开发的时候&#xff0c;我们需要注意MCU的数据存储模式&#xff0c;在嵌入式中有两种不同的存储模式&#xff0c;分别是 大端模式和小端模式。 …

dameng数据库数据id decimal类型,精度丢失

问题处理 这一次也是精度丢失&#xff0c;但是问题呢还是不一样&#xff0c;这一次所有的id都被加一了&#xff0c;只有id字段被加一&#xff0c;还有的查询查出来封装成对象之后对象的id字段被减一了&#xff0c;数据库id字段使用的decimal&#xff08;20,6&#xff09;&…

Apache Airflow (六) :DAG catchup 参数设置

&#x1f3e1; 个人主页&#xff1a;IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 &#x1f6a9; 私聊博主&#xff1a;加入大数据技术讨论群聊&#xff0c;获取更多大数据资料。 &#x1f514; 博主个人B栈地址&#xff1a;豹哥教你大数据的个人空间-豹…

软件测试 —— 常见的自动化测试架构!

一个自动化测试架构就是一个集成体系&#xff0c;其中定义了一个特殊软件产品的自动化测试规则。这一体系中包含测试功能函数库、测试数据源、测试对象识别标准&#xff0c;以及各种可重用的模块。这些组件作为小的构建模块&#xff0c;被组合起来代表某种商业流程。自动化测试…

求最大公约数math.gcd()

【小白从小学Python、C、Java】 【计算机等级考试500强双证书】 【Python-数据分析】 求最大公约数 math.gcd() [太阳]选择题 下列代码执行输出的结果是&#xff1f; import math print("【执行】print(math.gcd(6, 8))") print(math.gcd(6, 8)) print(&quo…

【汇编】汇编语言的介绍

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、汇编是什么&#xff1f;二、为什么要学习汇编语言&#xff1f;三、学习汇编语言的好处四、安装汇编环境4.1 下载虚拟环境4.2 配置虚拟环境 总结 前言 计算…

我的创作纪念日-我在csdn的三周年

文章目录 机缘收获日常成就憧憬 机缘 2020 年 11 月 09 日&#xff0c;撰写了第 1 篇技术博客&#xff0c;到现在不知不觉三周年了。 慢慢的也会将自己的感受和知识梳理成专栏&#xff0c;记录日常的学习以及通过文章进行技术交流&#xff0c;和大家分享一个我认为比较好的成…

Unity Hub无法登陆的两种终极解决办法

最近换了个电脑&#xff0c;需要重装Unity&#xff0c; 然后unity hub 怎么都无法登陆&#xff0c;登陆不了就不能激活personal license。试了很多次&#xff0c;包括unity hub 2.5.8 和unity hub 3.3都不行&#xff0c;真的是很崩溃。因为是公司的电脑&#xff0c;限制比较多&…

西门子精智屏数据记录U盘插拔问题总结

西门子精智屏数据记录U盘插拔问题总结 注意: 数据记录过程中不允许带电插拔 U 盘! 数据记录的相关功能可参考以下链接中的内容: TIA博途wincc V16 如何进行变量周期归档?

AI大模型低成本快速定制秘诀:RAG和向量数据库

文章目录 1. 前言2. RAG和向量数据库3. 论坛日程4. 购票方式 1. 前言 当今人工智能领域&#xff0c;最受关注的毋庸置疑是大模型。然而&#xff0c;高昂的训练成本、漫长的训练时间等都成为了制约大多数企业入局大模型的关键瓶颈。 这种背景下&#xff0c;向量数据库凭借其独特…

算法笔记-第七章-栈的应用(未完成)

算法笔记-第七章-栈的应用 栈的基本常识栈的解释一栈的解释二 栈的操作序列合法的出栈序列可能的出栈序列补充知识点 后缀表达式&#xff08;无优先级&#xff09; 栈的基本常识 栈&#xff08;Stack&#xff09;是只允许在一端进行插入或删除操作的线性表。 栈的解释一 栈的…

基础大模型的结构特性与发展

摘要&#xff1a; 基础大模型的结构特性是什么给予的&#xff1f;在建模部分&#xff0c;我们将探索基础模型背后的底层架构&#xff0c;并确定5个关键属性。 首先&#xff0c;我们从讨论计算模型的表现力开始-捕获和吸收真实世界的信息&#xff0c;以及可扩展性-熟练地处理大量…

类和对象(4):Date类.运算符重载 1

一、赋值运算符重载 1.1 运算符重载 运算符重载是具有特殊函数名的函数&#xff0c;函数名字为&#xff1a;关键词operator需要重载的运算符符号。 不能重载C/C中未出现的符号&#xff0c;如&#xff1a;operator。重载操作符必须有一个类类型参数。不能改变用于内置类型运算…