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){//当链表后段不为空时,(为空不走这一步,否则空指针异常),链表的最后需要手动置为null
            latterend.next = null;
        }
        formerend.next = latterhead;//之所以上面要求formerend全程不为空,是因为这一步会报异常,null
        return 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,另一个为B
        if(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同时向入口处走,相遇的地方就是要返回的点.

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

动态演示

寻找环的入口

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

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

相关文章

【AXIS】AXI-Stream FIFO设计实现(四)——异步时钟

前文介绍了几种同步时钟情况下的AXI Stream FIFO实现方式&#xff0c;一般来说&#xff0c;FIFO也需要承担异步时钟域模块间数据传输的功能&#xff0c;本文介绍异步AXIS FIFO的实现方式。 如前文所说&#xff0c;AXI-Stream FIFO十分类似于FWFT异步FIFO&#xff0c;推荐参考前…

书生浦语笔记一

2023年6月&#xff0c;InternLM的第一代大模型正式发布。仅一个月后&#xff0c;该模型以及其全套工具链被开源。随后&#xff0c;在8月份&#xff0c;多模态语料库chat7B和lagent也被开源。而在接下来的9月份&#xff0c;InternLM20B的开源发布进一步加强了全线工具链的更新。…

《剑指 Offer》专项突破版 - 面试题 98、99 和 100 : 和动态规划相关的矩阵路径问题(C++ 实现)

目录 前言 面试题 98 : 路径的数目 面试题 99 : 最小路径之和 面试题 100 : 三角形中最小路径之和 前言 矩阵路径是一类常见的可以用动态规划来解决的问题。这类问题通常输入的是一个二维的格子&#xff0c;一个机器人按照一定的规则从格子的某个位置走到另一个位置&#…

软件杯 深度学习YOLOv5车辆颜色识别检测 - python opencv

文章目录 1 前言2 实现效果3 CNN卷积神经网络4 Yolov56 数据集处理及模型训练5 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习YOLOv5车辆颜色识别检测 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0…

Java 面试宝典:请说下你对 Netty 中Reactor 模式的理解

大家好&#xff0c;我是大明哥&#xff0c;一个专注「死磕 Java」系列创作的硬核程序员。 本文已收录到我的技术网站&#xff1a;https://skjava.com。有全网最优质的系列文章、Java 全栈技术文档以及大厂完整面经 回答 Reactor 模式是一种高效处理并发网络事件的设计模式&…

SQLite3进行数据库各项常用操作

目录 前言1、SQLite介绍2、通过SQLite创建一个数据库文件3、往数据库文件中插入数据4、数据库文件信息查询5、修改数据库中的内容6、删除数据库中的内容 前言 本文是通过轻量化数据库管理工具SQLite进行的基础操作和一些功能实现。 1、SQLite介绍 SQLite是一个广泛使用的嵌入…

GEE土地分类——基于遥感影像数据的不同作物的分类

简介 这里我们首先要更改原始代码的中的影像和研究区矢量的问题,这个为了防止我们计算的过程超限,建议先将我们的研究区影像和样本点先存在自己的assets中,然后导入到新的脚本中。然周本文就是对其进行影像进行归一化处理,然后进行样本点值提取至点,然后训练样本点,进行…

系统架构体系

一、单体架构 1.浏览器&#xff0c;DNS服务器&#xff08;解析域名&#xff0c;转换为IP地址&#xff09;&#xff0c;一台计算机就相当于一个服务器&#xff08;用端口号进行区分Tomcat&#xff08;web服务&#xff09;&#xff0c;数据库服务&#xff09; 2.本次架构解决…

3D转换1111

1.三维坐标系 1.3D位移: translate3d(x,y,z)  translform:translateX(100px)&#xff1a;仅仅是在x轴上移动  translform:translateY(100px)&#xff1a;仅仅是在Y轴上移动  translform:translateZ(100px)&#xff1a;仅仅是在Z轴上移动&#xff08;注意&#xff1…

HTTP/1.1 如何优化?(计算机网络)

有三种方法&#xff1a; 第一个思路是&#xff0c;通过缓存技术来避免发送 HTTP 请求。客户端收到第一个请求的响应后&#xff0c;可以将其缓存在本地磁盘&#xff0c;下次请求的时候&#xff0c;如果缓存没过期&#xff0c;就直接读取本地缓存的响应数据。如果缓存过期&#…

Uibot6.0 (RPA财务机器人师资培训第6天 )发票验真机器人案例实战

类似于小北的这篇博客&#xff1a;Uibot (RPA设计软件&#xff09;Mage AI智能识别&#xff08;发票识别&#xff09;———课前材料五_uibot 添加mageai-CSDN博客https://blog.csdn.net/Zhiyilang/article/details/135591297?spm1001.2014.3001.5501训练网站&#xff1a;泓江…

122、内网安全——域信息收集应用网络凭据CS插件AdfindBloodHound

文章目录 理解域域信息搜集 理解域 假设有1000台计算机&#xff0c;运维人员需要为每一台计算机进行软件的安装、环境部署&#xff0c;实际上运维人员不可能亲自对每一台计算机进行软件的安装和环境部署。实际&#xff0c;将所有1000台计算机放入一个域中&#xff0c;域内有一…

简单爬虫,爬取某东某商品评论前十页

商品链接地址&#xff1a;【博世四坑5系 6x100x160】博世&#xff08;BOSCH&#xff09;四坑5系&#xff08;1支装&#xff09;圆柄两坑两槽混凝土钻头 6x100x160mm【行情 报价 价格 评测】-京东 首先抓包&#xff0c;用搜索框搜索评论&#xff0c;看评论在哪个包中 为了好看筛…

Python - 深度学习系列31 - ollama的搭建与使用

说明 做这个的主要目的是为了搭建Langchain的本地环境&#xff0c;使用LangChain让LLM具备调用自定义函数的功能。 内容 1 安装server 以下将ollama的安装方式&#xff0c;以及使用做一个简单的说明(记录&#xff09;。之前对这个工具没有了解&#xff0c;只是从快速实践的…

【python】pip清华大学镜像

1、修改pip源为清华源&#xff1a; pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple2、结果是自动给我创建了一个文件&#xff1a; 3、打开这个文件所在的文件夹&#xff1a; 4、打开文件&#xff1a; 5、如果不想指定清华的&#xff0c;就删掉…

微信小程序引导组件【添加到我的小程序】

微信小程序引导组件&#xff0c;点击按钮&#xff0c;弹窗引导用户【添加到我的小程序】 源代码 https://ext.dcloud.net.cn/plugin?id17303

算法学习——LeetCode力扣图论篇3(127. 单词接龙、463. 岛屿的周长、684. 冗余连接、685. 冗余连接 II)

算法学习——LeetCode力扣图论篇3 127. 单词接龙 127. 单词接龙 - 力扣&#xff08;LeetCode&#xff09; 描述 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk&#xff1a; 每一对相…

动态内存管理-错题合集讲解

空指针的解应用操作&#xff08;错误信息合集&#xff09; 越界访问 首先我们上一个代码&#xff0c;看看这个的代码的问题 这个代码的问题显而易见 &#xff0c;就是在循环里面&#xff0c;产生了越界访问的问题&#xff0c;这里你开辟了10个整形空间&#xff0c;但是从0-1…

爬虫的验证码处理

1.我们先进入chrome浏览器的审查页面找到input方法&#xff1a; 为了不少找到一个input&#xff0c;我们ctrlf的方法输入input来查找 看见我们有6个需要输入的参数。 除了上面几个的input参数&#xff0c;我们还需要获取验证码的图片&#xff0c;后续要将字母填入进去。 二.安…

XDMA windos 编译

1、先安装 Visual Studio 2019 2、Download the Windows Driver Kit (WDK) - Windows drivers | Microsoft Learn 以前的 WDK 版本和其他下载 - Windows 驱动程序 |Microsoft学习 注意版本&#xff1a;下载2004的版本 3、 选择使用10.0.19041.0 安装这个sdk. 先按vs2019 然后…