Java链表LinkedList经典题目

一.LinkedList的方法

首先先看一下链表的方法:

方法解释
boolean add(E e)尾插
void add(int index, E element)将 e 插入到 index 位置
boolean addAll(Collection c)尾插 c 中的元素
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标 index 位置元素
E set(int index, E element)将下标 index 位置元素设置为 element
void clear()清空
boolean contains(Object o)判断 o 是否在线性表中
int indexOf(Object o)返回第一个 o 所在下标
int lastIndexOf(Object o)返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)截取部分 list

二.反转链表

题目对应LeetCode:206. 反转链表

/**
 * 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) {
        if(head==null || head.next==null){
            return head;
        }
        
        ListNode pr=head;
        ListNode cur=head.next;
        ListNode p=cur.next;

        while(cur!=null){
            cur.next=pr;

            pr=cur;
            cur=p;
            if(p!=null){
                p=p.next;
            }
        }

        head.next=null;

        return pr;
    }
}

思路:从前往后将每一个节点的next改成其前一个节点。

定义三个ListNode变量指向三个节点,cur指向的是当前要改变next的节点,pr指向的是cur.next要指向的节点,p是记录的作用,如果cur的next变成指向前面了,那么本来cur后面一个节点就丢失了,无法完成反转。

三.快慢指针在链表的应用

不少题目的解题关键就在快慢指针。

首先是最经典的应用:LeetCode:876. 链表的中间结点

题目意思就是返回中间结点,最笨的办法就是将链表遍历一遍,看看有多少个结点,然后再遍历出中间结点。这里使用快慢指针可以一步到位。

/**
 * 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 middleNode(ListNode head) {
        if(head==null){
            return head;
        }

        ListNode slow=head;
        ListNode fast=head;

        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }

        return slow;
    }
}

定义一个快指针和一个慢指针,让快的一下走两步,慢的一下走一步,这样走到最后停止时,slow刚好在中间结点上。

这个可以说是一个元问题,很多链表的题目都有这道题快慢指针的影子。

像非常经典的回文链表问题:CR 027. 回文链表,用的都是快慢指针的思想。

四.相交链表

题目对应LeetCode:160. 相交链表

这是题目的描述:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

由例图可以看出,在两个单链表相遇之后,交点后面的结点都是相同的。先考虑最简单的情况,如果两个链表的长度相同,那么直接从头开始一个一个遍历,知道找到交点。但是这个方法在双方长度不一时用不了。既然用不了,那我们就借着这个思路改一下,给短的链表补上不就行了,换句话说,链表从后往前对齐,长链表前面多的那部分不可以有结点,直接跳过即可,这样问题就解决了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null && headB==null){
            return null;
        }

        int len=0;
        int lb=0;
        int la=0;

        ListNode cur=headA;
        while(cur!=null){
            la++;
            cur=cur.next;
        }

        cur=headB;
        while(cur!=null){
            lb++;
            cur=cur.next;
        }

        ListNode l=headA;
        ListNode s=headB;
        len=la-lb;
        if(la<lb){
            l=headB;
            s=headA;
            len=lb-la;
        }

        while(len!=0){
            l=l.next;
            len--;
        }

        while(l!=s && l!=null && s!=null){
            l=l.next;
            s=s.next;
        }

        if(l==s && l!=null){
            return l;
        }else{
            return null;
        }
    }
}

五.链表的环问题

1.是否存在环

题目对应LeetCode:141. 环形链表

应用的也是快慢指针的思想,这个就像在操场上跑步一样,如果一快一慢,而且还是闭环的话,那么两个人一定会相遇。这个同理,如果成环,那么两个指针也是会相遇的。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode slow=head;
        ListNode fast=head;

        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;

            if(slow==fast){
                return true;
            }
        }
        return false;
    }
}

2.返回入环后的第一个结点

题目对应LeetCode:142. 环形链表 II

这个题里面有一个数学推导,直接说结果,起点到入环后第一个结点的距离=快慢指针相遇的交点到入环后第一个结点的距离。

这个推导并不难,就初中生水平,大家可以自己试一下。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;

        while(true){

            if(fast==null || fast.next==null){
                return null;
            }
            
            slow=slow.next;
            fast=fast.next.next;

            if(fast==slow){
                break;
            }
        }

         slow=head;

        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }

        return slow;
    }
}

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

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

相关文章

【7.10更新】Win11 23H2 正式版:22631.3880镜像下载!

微软向Win11 23H2用户推送了七月最新更新补丁KB5040442&#xff0c;系统更新后&#xff0c;版本号将升至22631.3880。本次更新包括了一些安全质量更新&#xff0c;并修复了6月可选更新导致的任务栏无法加载、交互问题&#xff0c;建议大家更新。该版本系统离线制作而成&#xf…

Spring MVC入门2

Postman的使用 接上期我们抛出了一个问题&#xff0c;Postman的使用 可以点击链接下载 https://www.postman.com/downloads/ 安装之后会提示版本升级&#xff0c;直接点击dissmiss即可。 要想发送数据&#xff0c;具体歩奏如下简图&#xff1a; 还有一个更具体的图&#xff…

回归树模型

目录 一、回归树模型vs决策树模型&#xff1a;二、回归树模型的叶结点&#xff1a;三、如何决定每个非叶结点上的特征类型&#xff1a; 本文只介绍回归树模型与决策树模型的区别。如需了解完整的理论&#xff0c;请看链接&#xff1a;决策树模型笔记 一、回归树模型vs决策树模…

jpg图片怎么转成png格式?学会这四种方法,轻松完成图片转换!

jpg图片怎么转成png格式&#xff1f;在数字图像的广袤天地中&#xff0c;JPG与PNG两大格式如同两位各具魅力的艺术家&#xff0c;各自以其独特的风格赢得了人们的喜爱&#xff0c;JPG擅长运用有损压缩的技法&#xff0c;以牺牲部分图像细节为代价&#xff0c;打造出更小巧、更易…

卤味江湖中,周黑鸭究竟该抓住什么赛点?

近年来&#xff0c;卤味江湖的决斗从未停止。 随着休闲卤味、佐餐卤味等细分赛道逐渐形成&#xff0c;“卤味三巨头”&#xff08;周黑鸭、绝味食品、煌上煌&#xff09;的牌桌上有了更多新对手&#xff0c;赛道变挤了&#xff0c;“周黑鸭们”也到了转型关键期。 这个夏天&a…

tableau范围-线图与倾斜图绘制 - 14

范围-线图与倾斜图 1.范围-线图1.1 含义1.2 范围-线图1.2.1 折线图绘制1.2.2 设置计算字段1.2.3 添加详细信息1.2.4 添加参考线1.2.5 结果 2. 倾斜图2.1 含义2.2 倾斜图绘制2.2.1 数据导入2.2.2 创建计算字段2.2.3 排名编辑表计算2.2.4 显示标签2.2.5 标签格式设置2.2.6 修改排…

4.感知机

感知机 ​ 给定输入 x x x&#xff0c;权重 w w w&#xff0c;和偏移 b b b,感知机输出&#xff1a; KaTeX parse error: Unknown column alignment: o at position 16: \begin{array} o̲ \sigma(<w,x>… 或者是二分类&#xff1a;-1或1 Expected node of symbol gro…

【异常】JDK21报错NoSuchFieldError: Class com.sun.tools.javac.tree.JCTree$JCImport does not have member fie

【异常】JDK21报错NoSuchFieldError: Class com.sun.tools.javac.tree.JCTree$JCImport does not have member fie java: java.lang.NoSuchFieldError: Class com.sun.tools.javac.tree.JCTree$JCImport does not have member field com.sun.tools.javac.tree.JCTree qualid …

鸿蒙开发:Universal Keystore Kit(密钥管理服务)【HMAC(C/C++)】

HMAC(C/C) HMAC是密钥相关的哈希运算消息认证码&#xff08;Hash-based Message Authentication Code&#xff09;&#xff0c;是一种基于Hash函数和密钥进行消息认证的方法。 在CMake脚本中链接相关动态库 target_link_libraries(entry PUBLIC libhuks_ndk.z.so)开发步骤 生…

Windows netstat命令详解,Windows查看网络连接

「作者简介」&#xff1a;冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础著作 《网络安全自学教程》&#xff0c;适合基础薄弱的同学系统化的学习网络安全&#xff0c;用最短的时间掌握最核心的技术。 netstat 常用来…

某客户管理系统Oracle RAC节点异常重启问题详细分析记录

一、故障概述 某日10:58分左右客户管理系统数据库节点1所有实例异常重启&#xff0c;重启后业务恢复正常。经过分析发现&#xff0c;此次实例异常重启的是数据库节点1。 二、故障原因分析 1、数据库日志分析 从节点1的数据库日志来看&#xff0c;10:58:49的时候数据库进程开始…

20240711编译友善之臂的NanoPC-T6开发板的Buildroot

20240711编译友善之臂的NanoPC-T6开发板的Buildroot 2024/7/11 21:02 百度&#xff1a;nanopc t6 wiki https://wiki.friendlyelec.com/wiki/index.php/NanoPC-T6/zh NanoPC-T6/zh 4.4 安装系统 4.4.1 下载固件 4.4.1.1 官方固件 访问此处的下载地址下载固件文件 (位于网盘的&q…

每日刷题(二分图,二分查找,dfs搜索)

目录 1.P3853 [TJOI2007] 路标设置 2.P1129 [ZJOI2007] 矩阵游戏 3.P1330 封锁阳光大学 4.Trees 5.P1141 01迷宫 1.P3853 [TJOI2007] 路标设置 P3853 [TJOI2007] 路标设置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先求出每个路标之间的距离&#xff0c;再二分查找每…

妙笔生词智能写歌词软件:科技赋能艺术还是冲淡原味?

在当今数字化的时代&#xff0c;科技的触角延伸至艺术创作的各个领域&#xff0c;妙笔生词智能写歌词软件便是其中一个引人瞩目的产物。然而&#xff0c;它的出现引发了一场关于科技与艺术关系的深刻思考&#xff1a;究竟是为艺术创作赋予了新的能量&#xff0c;还是在不经意间…

【密码学】哈希函数与加密算法的关系

一、哈希函数的定义 哈希函数&#xff08;Hash Function&#xff09;&#xff0c;也被称为散列函数或杂凑函数&#xff0c; 是一种将任意长度的输入数据&#xff08;通常称为“预映射”或“消息”&#xff09;转换为固定长度输出&#xff08;通常称为“哈希值”、“散列值”、“…

软链接node_modules

公司项目很多微应用的子项目公用同一套模板&#xff0c;也就会使用同一个node_modules 1.先创建3个同样的项目,并安装一个其中的一个node_modules给他丢到外边 2.win r -------> cmd --------> ctrlshift enter(已管理员身份打开cmd) 3.在窗口分别执行以下代码…

医学王者刊!影响因子自创刊只增不减,3区跃升1区,国人发文占比6成!

【SciencePub学术】今天给大家推荐的是一本医学领域的SCI&#xff0c;是1本颇富潜力的国产期刊。影响因子自创刊以来就逐年上涨&#xff0c;凭借自己的努力从中科院3区跃迁至中科院1区&#xff0c;据说很多人已经靠信息差吃上了这本期刊的红利&#xff0c;接下来给大家解析一下…

卷积是如何计算的

使用代码&#xff0c;看卷积是如何计算的。 torch.nn torch.nn.functional srtide 的用法&#xff0c;代表卷积核的步幅 import torch import torch.nn.functional as F # 这个是输入的一个二维矩阵 input torch.tensor([[1,2,0,3,1],[0,1,2,3,1],[1,2,1,0,0],[5,2,3,1,1],…

SpringBoot相关

SpringBoot 1. what springboot也是spring公司开发的一款框架。为了简化spring项目的初始化搭建的。 spring项目搭建的缺点&#xff1a; 配置麻烦依赖繁多tomcat启动慢 2 .springboot的特点(why) 自动配置 springboot的自动配置是一个运行时(更准确地说&#xff0c;是应用程…

【学术会议征稿】第三届人工智能与智能信息处理国际学术会议(AIIIP 2024)

第三届人工智能与智能信息处理国际学术会议&#xff08;AIIIP 2024&#xff09; 2024 3rd International Conference on Artificial Intelligence and Intelligent Information Processing 第三届人工智能与智能信息处理国际学术会议&#xff08;AIIIP 2024&#xff09;将于…