Collection与数据结构 链表与LinkedList(三):链表精选OJ例题(下)

1. 分割链表

OJ链接
在这里插入图片描述

class Solution {public ListNode partition(ListNode head, int x) {if(head == null){return null;//空链表的情况}ListNode cur = head;ListNode formerhead = null;ListNode formerend = null;ListNode latterhead = null;ListNode latterend = null;//定义链表分区while (cur != null){//遍历链表if(cur.val < x){if(formerhead == null){formerhead = cur;formerend = cur;//第一次遍历头和尾都为null//formerend = formerend.next;错误,不可以使得formerend向下走,否者为null,会空指针异常}else{formerend.next = cur;formerend = formerend.next;//formerend全程不可以为空}}if(cur.val >= x){if(latterhead == null){latterhead = cur;latterend = cur;}else{latterend.next = cur;latterend = latterend.next;}}cur = cur.next;}if(formerhead == null){//链表前段位空时的情况,formerend为空,下面会报异常return latterhead;}if(latterhead != null){//当链表后段不为空时,(为空不走这一步,否则空指针异常),链表的最后需要手动置为nulllatterend.next = null;}formerend.next = latterhead;//之所以上面要求formerend全程不为空,是因为这一步会报异常,nullreturn formerhead;}
}

整体思路:
创建一个新的链表,把这个新的链表用x分段,遍历原链表,根据条件把结点放入新链表,之后把前面一段链表和后面一段链表连接起来.

[注意事项]

  1. 要始终保持fe(formerend)不为空,否者在最后连接的时候就要报空指针异常
  2. 考虑几种特殊情况
  • 链表为空,返回null
  • 前半段链表为空,在最后连接的时候会报空指针异常,所以在最后的时候返回lb即可.
  • 当后半段链表不为空的时候,最后一个结点的next有可能不为null,所以要对最后手动置空,否者会越界.

动态演示

分割链表

2. 回文链表

OJ链接
在这里插入图片描述

class Solution {public boolean isPalindrome(ListNode head) {if(head == null){//空链表情况下return true;}ListNode fast = head;ListNode slow = head;ListNode cur = null;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;//找到中间结点}cur = slow.next;while(cur != null){ListNode curNext = cur.next;//在循环体中定义ListNode,防止空指针异常cur.next = slow;slow = cur;cur = curNext;}//翻转后半段链表cur = head;while(cur != slow){//奇数判断回文if(cur.val != slow.val){return false;}if(cur.next == slow){//偶数判断回文return true;}cur = cur.next;slow = slow.next;}return true;}
}

整体思路:
先使用快慢指针找到中间节点,之后将后半段链表使用头插法翻转.之后把head和slow向中间遍历,相遇就是回文.

[注意事项]

  1. 注意区分奇偶数,奇数整体思路没问题,但是偶数永远不会相遇,此时就需要引入if(cur.next == slow)判断偶数情况.

动态演示

回文链表(偶数)

回文链表(奇数)

3. 相交链表

OJ链接
在这里插入图片描述

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA = 0;int lenB = 0;ListNode cur = headA;while(cur != null){lenA++;cur = cur.next;}cur = headB;while(cur != null){lenB++;cur = cur.next;}//计算两个链表的长度int len = lenA-lenB;//计算长度之差,但是有可能为负数ListNode longList = headA;ListNode shortList = headB;//定义长链表和短链表,如果len为正,则longList为A,另一个为Bif(len < 0){//负数则相反longList = headB;shortList = headA;len = lenB-lenA;//把len变为正数}while(len != 0){longList = longList.next;len--;//先让长链表走差值步}while(longList != shortList){longList = longList.next;shortList = shortList.next;//之后一起走,直到相交}if(longList == null || shortList == null){return null;//没有交点的情况}return longList;//返回交点}
}

整体思路
先让长链表走短链表与长链表的差值步,之后一起走,相遇之后就有交点.

[注意事项]

  1. 不确定哪个链表长,哪个链表短,所以长度的差值可能为负数.我们定义长链表和短链表来解决这个问题,利用长度的差值来判断长短.
  2. 有一个非常隐形的问题,链表可能不想交,所以我们要用if(longList == null || shortList == null)来限制.虽然没有这句话也可以跑过,是因为最后longList和shortList都走到了null,返回longList正好也是null.所以这个问题非常隐性.

动态演示

相交链表

4. 环形链表

OJ链接
在这里插入图片描述

ublic class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){//先以无环作为跳出循环的条件,因为是快指针,所以两个条件缺一不可fast = fast.next.next;slow = slow.next;if(slow == fast){//在走的过程中再判断什么时候相等,返回即可return true;}}return false;}
}

整体思路
定义一个快指针,一个慢指针,快指针一次走两步,慢指针一次走一步,最终进入环的时候必定会相遇.相遇一定就有环.

[注意事项]

  1. 首先判断的是链表有没有环,这是循环的条件.
  2. 在循环体内部再判断会不会相遇.

动态演示

环形链表

5. 寻找环形链表的环入口

OJ链接
在这里插入图片描述

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){//无环情况fast = fast.next.next;slow = slow.next;if(fast == slow){//相遇的情况while(head != slow){head = head.next;slow = slow.next;//向环的入口靠近}return slow;//相遇的位置即为入口}}return null;}
}

整体思路
先找到相遇的点,之后根据数学推导可知,链表头到入口的距离与相遇点到入口的距离相等,让head和slow同时向入口处走,相遇的地方就是要返回的点.

[数学推导]
在这里插入图片描述

动态演示

寻找环的入口

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机网络-HTTP相关知识-RSA和ECDHE及优化

HTTPS建立基本流程 客户端向服务器索要并验证服务器的公钥。通过密钥交换算法&#xff08;如RSA或ECDHE&#xff09;协商会话秘钥&#xff0c;这个过程被称为“握手”。双方采用会话秘钥进行加密通信。 RSA流程 RSA流程包括四次握手&#xff1a; 第一次握手&#xff1a;客户…

Python可视化之Matplotlib

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言1、解决坐标轴刻度负号乱码2、解决中文乱码问题3、图形展现形式 一、图形绘制1.折线图plot2.散点图plot&scatter3.柱状图plt.bar&条形图plt.barh4.直方…

探索设计模式的魅力:简单工厂模式

个人主页: danci_ &#x1f525;系列专栏&#xff1a;《设计模式》《MYSQL应用》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 &#x1f680; 转载自热榜文章&#xff1a;探索设计模式的魅力&#xff1a;简单工厂模式 简单工厂模式&#x…

Prometheus+grafana环境搭建MongoDB(docker+二进制两种方式安装)(五)

由于所有组件写一篇幅过长&#xff0c;所以每个组件分一篇方便查看&#xff0c;前四篇mongodb的exporter坑也挺多总结一下各种安装方式&#xff0c;方便后续考古。 Prometheusgrafana环境搭建方法及流程两种方式(docker和源码包)(一)-CSDN博客 Prometheusgrafana环境搭建rabb…

Redis面试题28道

1、什么是类加载器&#xff0c;类加载器有哪些&#xff1f; 1、什么是类加载器&#xff1f; 类加载器负责加载所有的类&#xff0c;其为所有被载入内存的类生成一个 java.lang.Class 实例对象。 2、类加载器有哪些&#xff1f; JVM 有三种类加载器&#xff1a; &#xff08…

软考--软件设计师(软件工程总结2)

目录 1.测试方法 2.软件项目管理 3.软件容错技术 4.软件复杂性度量 5.结构化分析方法&#xff08;一种面向数据流的开发方法&#xff09; 6.数据流图 1.测试方法 软件测试&#xff1a;静态测试&#xff08;被测程序采用人工检测&#xff0c;计算机辅助静态分析的手段&…

GraphSage

背景 大型图中节点的低维嵌入在各种预测任务中非常有用。GraphSage是一种通用的归纳框架&#xff0c;它利用节点特征信息&#xff08;例如&#xff0c;文本属性&#xff09;有效地为以前看不见的数据生成节点嵌入。相比于对每个节点训练单独的嵌入&#xff0c;GraphSage学习了一…

Hyper-v平台搭建pve系统之网络配置(双网卡、内外网分离)

现在我需要在我本地配置的PVE系统上配置双网卡&#xff0c;然后一个连接外部网络&#xff08;访问互联网&#xff09;&#xff0c;一个连接内部网络&#xff08;只能和宿主机之间互相访问&#xff09; 最终效果&#xff1a; 登录PVE平台&#xff0c;我可以正常访问外网&#…

用html写一个爱心

<!DOCTYPE html> <html lang"zh-CN"><head><meta http-equiv"Content-Type" content"text/html; charsetUTF-8" /><title>爱您</title><style>* {padding: 0;margin: 0;}body {background-color: pin…

铁山靠之数学建模-基础篇

小黑子的数模基础篇 一、什么是数学建模1.1 数学模型分类1.2 备战准备什么1.3 组队学习路线1.4 赛前准备1.5 赛题选择1.5.1 赛题类型1.5.2 ABC赛题建议 1.6 学会查询1.6.1 百度搜索技巧1.6.2 查文献1.6.3 数据预处理 1.7 建模全过程 二、数模论文2.1 论文排版2.2 标题怎么写2.3…

前端学习之BOM编程-window对象、history对象、navigator对象、location对象

window对象 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>widnow对象</title><style>div{width: 2000px;height: 4000px;background-image: linear-gradient(to bottom right,red,blue…

JVM调优参数介绍

堆配置 -Xms:初始堆大小 -Xms&#xff1a;最大堆大小 -XX:NewSizen:设置年轻代大小 -XX:NewRation:设置年轻代和年老代的比值。如&#xff1a;为3表示年轻代和年老代比值为1&#xff1a;3&#xff0c;年轻代占整个年轻代年老代和的1/4 -XX:SurvivorRation:年轻代中Eden区与…

计组第三版书例题

基础知识过一下 存储器与CPU的连接主要通过数据总线、地址总线和控制总线实现。CPU首先向存储器发送地址信号&#xff0c;然后发出读写控制信号&#xff0c;最后在数据总线上进行数据的读写操作 。这种连接方式确保了CPU能够正确地访问和控制存储器中的数据。 https://blog.cs…

ES6学习(五)-- Module 语法

文章目录 Module 语法1.1 痛点介绍(1) 异步加载(2) 私密(3) 重名(4) 依赖 1.2 解决方法(1) 解决异步加载问题(2) 解决私密问题(3) 重名解决方法(4) 解决依赖问题 1.3 模块化使用案例 Module 语法 之前js 出现的某些痛点&#xff1a; 在script 中引入的变量名不可以重复&#…

Day:003 | Python爬虫:高效数据抓取的编程技术(爬虫基础)

urllib发送get请求 在目前网络获取数据的方式有多种方式&#xff1a;GET方式大部分被传输到浏览器的html&#xff0c;images, js,css, … 都是通过GET 方法发出请求的。它是获取数据的主要方法 例如&#xff1a;www.baidu.com 搜索 Get请求的参数都是在Url中体现的,如果有中…

SQLAlchemy 建立数据库模型之间的关系

常见关系&#xff1a; 一对多关系多对一关系多对多关系一对一关系 一对多关系&#xff08;一个作者&#xff0c;多篇文章&#xff09; ## 一对多关系&#xff0c;单作者-多文章&#xff0c;外键不可少 ## 外键(ForeignKey)总在多的那边定义,关系(relationship)总在单的那边定…

12-项目部署_持续集成

项目部署_持续集成 1 今日内容介绍 1.1 什么是持续集成 持续集成&#xff08; Continuous integration &#xff0c; 简称 CI &#xff09;指的是&#xff0c;频繁地&#xff08;一天多次&#xff09;将代码集成到主干 持续集成的组成要素 一个自动构建过程&#xff0c; 从…

华为ensp中ospf多区域管理 原理及配置命令(详解)

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; ————前言———— OSPF 多区域的主要作用是缩小链路状态数据库和路由表的规模&#xff0c;减少路由更新的频率&#xff0c;提高网络的可扩展性&#xff0c;实现路由过滤和路由汇总&#xff0…

【计算机网络】应用层——HTTP协议详解

文章目录 1. HTTP协议简介2. Fiddler简介&#xff08;抓包工具&#xff09;2.1 安装Fiddler2.2 使用Fiddler进行抓包2.3 Fiddler的工作原理 3. HTTP协议的报文格式4. HTTP 请求4.1 HTTP请求首行4.2 认识 URL关于 URL encoding 4.3 认识“方法”GET方法POST方法GET和POST的区别关…

【linux】基础IO(二)

我们在基础IO&#xff08;一&#xff09;主要讲述了fd&#xff0c;一切皆文件&#xff0c;文件的系统调用与语言文件库函数的关系&#xff0c; 今天主要进行对重定向与缓冲区的理解与应用。另外&#xff0c;对系统调用的read进行一下使用。 read的使用&#xff1a; 再使用rea…