【Java--数据结构】链表经典OJ题详解(下)

前言

上一篇

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



目录

前言

链表分割 

链表的回文结构

 相交链表

环形链表


链表分割 

编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。OJ链接

1.定义一个节点cur遍历原链表,创建两个新链表B和A,用于放小于x和大于x的,最后将这两个链表连接构成一个新链表。这两个链表分别创建两个节点bs be和as ae,bs作为B链表的头节点,be用于添加节点,as和ae同理

2.比较每个节点的val与x的大小

若val<x,则该节点放在新链表B中

  • be.next=cur;
  • be=be.next;

其中要注意第一次插入be=bs=cur;

若val>x,则该节点放在新链表A中

  • ae.next=cur;
  • ae=ae.next;

其中要注意第一次插入ae=as=cur;

3.注意:

最后一个节点的next,没有null

要判断全部小于x,或全部大于等于x的情况(即遍历完原链表发现B链表为空或者A链表为空)

发现B链表为空 直接返回A链表 return as;

4.拼接

将B和A链表拼接,return bs;

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        // write code here
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;

        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    be=bs=cur;//第一次插入
                }else{
                    be.next=cur;
                    be=be.next;
                }
                cur=cur.next;
            }else{
                if(as==null){
                    as=ae=cur;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
                cur=cur.next;
            }
        }
        //第一部分是空返回第二部分,不为空 拼接
        if(bs==null){
            return as;
        }
        //进行拼接
        be.next=as;
        if(as!=null){//后半部分不为空,将后半部分置为空
            ae.next=null;
        }
        return bs;
    }
}

链表的回文结构

OJ链接

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构,给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

 1.找中间节点

快慢指针法(在上一篇有详细讲到),此时fast在走完了链表,slow在中间

2.反转中间节点以后的部分 (在上一篇也有详细讲到)

  • cur=slow.next;
  • while(cur!=null){
  • curN=cur.next;
  • cur.next=slow;
  • slow=cur;
  • cur=curN;}

反转链表后slow一定是尾节点

3.对比前后的val值

cur=slow.next

不能使用fast遍历(fast不一定是尾节点,当链表个数为偶数时,fast为空),所以用slow

注意:

偶数节点时,head和slow没有办法相遇

            //判断偶数情况
            if(head.next==slow){
                return true;
            }

 

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here
        //空链表也是回文的
        if(head==null){
            return true;
        }
        //1.找中间节点
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //2.反转中间节点之后的链表
        ListNode cur=slow.next;
        while(cur!=null){
        ListNode curN=cur.next;
        cur.next=slow;
        slow=cur;
        cur=curN;
        }
        //3.对比head和slow的val值
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            //判断偶数情况
            if(head.next==slow){
                return true;
            }
                head=head.next;
                slow=slow.next;
        }
            return true;
    }
}

 相交链表

输入两个链表,找出它们的第一个公共结点。OJ链接

 

链表相交后,形成Y结构链表,如图题目要求是找出值为60的节点

1.分别求2个链表的长度,求出差值x

2.让长的先走x步

3.然后一起走,直到相遇

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //假设p1是长链表
        ListNode p1=headA;
        ListNode p2=headB;
        int lenA=0;
        int lenB=0;
        while(p1!=null){
            p1=p1.next;
            lenA++;
        }
        while(p2!=null){
            p2=p2.next;
            lenB++;
        }
        //要重新让p1和p2指向头节点
        p1=headA;
        p2=headB;
        int len =lenA-lenB;
        if(len<0){
            p1=headB;
            p2=headA;
            len=lenB-lenA;
        }
        //走完上面代码后p1一定是最长的链表
        //让长链表先走len步
        for(int i=0;i<len;i++){
            p1=p1.next;
        }
        //一起走
        while(p1!=p2){
            p1=p1.next;
            p2=p2.next;
        }
        if(p1==null){
            //如果两个引用都为空,证明不相交,返回null  不写也不会报错
            return null;
        }
        return p1;
    }
}

环形链表

给定一个链表,判断链表中是否有环。 OJ链接

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

fast走一步,slow走两步,若相遇,则有环

public 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(fast==slow){
                return true;
            }
        }
        return false;
    }
}

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

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

相关文章

品深茶的抗癌效果怎么样?

茶叶中的一些成分&#xff0c;如茶多酚、儿茶素等&#xff0c;具有抗氧化和抗炎作用&#xff0c;这些作用在一定程度上可以抑制癌细胞的生长和扩散。 然而&#xff0c;这些成分在茶叶中的含量和生物利用率会受到多种因素的影响&#xff0c;如茶叶的品种、制作工艺、饮茶方式等…

【Redis 开发】Lua语言

Lua Lua语法 Lua语法 Lua是一种小巧的脚本语言&#xff0c;底层用C语言实现&#xff0c;为了嵌入式应用程序中 官网&#xff1a;https://www.lua.org/ 创建lua文件 touch hello.lua 运行lua文件 lua hello.lua 输出语句 print("Hello World!")数据类型 可以通过t…

idea常用知识点随记

idea常用知识点随记 1. 打开idea隐藏的commit窗口2. idea中拉取Git分支代码3. idea提示代码报错&#xff0c;项目编译没有报错4. idea中实体类自动生成序列号5. idea隐藏当前分支未commit代码6. idea拉取新建分支的方法 1. 打开idea隐藏的commit窗口 idea左上角File→Settings…

java连锁美业收银系统源码-美业SaaS系统【微信小程序端】功能及应用场景介绍

博弈美业管理系统源码 连锁多门店美业收银系统源码 多门店管理 / 会员管理 / 预约管理 / 排班管理 / 商品管理 / 促销活动 PC管理后台、手机APP、iPad APP、微信小程序 &#xff08; 需要系统演示视频可联系观看 &#xff09; ▶ 顾客微信小程序端&#xff1a; 场景名称 场…

React配置@别名路径配置

1. 背景知识 路径解析配置&#xff08;webpack&#xff09;&#xff0c;把 / 解析为 src/路径联想配置&#xff08;VsCode&#xff09;&#xff0c;VsCode 在输入 / 时&#xff0c;自动联想出来对应的 src/下的子级目录 2. 路径解析配置 配置步骤&#xff1a; 安装craco npm …

利用Seaborn实现高级统计图表—python可视化

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 利用 Seaborn 实现高级统计图表 在数据可视化领域&#xff0c;Seaborn 是 Python 中一个备…

ArcGIS小技巧—坐标系匹配

坐标系&#xff1a;&#xff08;Coordinate System&#xff09;&#xff1a;在一些书籍和软件中也叫做空间参考&#xff0c;简单来说&#xff0c;有了坐标系&#xff0c;我们才能够用一个或多个“坐标值”来表达和确定空间位置。没有坐标系&#xff0c;坐标值就无从谈起&#x…

c#数据库:1.c#创建并连接数据库

安装软件:SQL Server Management Studio Management Studio Visual Studio 2022 启动服务: 打开SQL Server Management Studio Management Studio ,连接到服务器(GUANZU是我的计算机名) 新建数据库,随便起个名字叫aq: c#代码: using System; using System.Collections.Gener…

Detla lake with Java--在spark集群上运行程序

昨天写了第一篇入门&#xff0c;今天看见有人收藏&#xff0c;继续努力学习下去。今天要实现的内容是如何将昨天的HelloDetlaLake 在spark集群上运行&#xff0c;。具体步骤如下 1、安装spark,我使用的是 spark-3.5.1-bin-hadoop3-scala2.13&#xff0c;去官网下载&#xff0c…

C++ 如何实现原子性

1.操作系统如何实现原子性 在单处理器,单核,运行多线程的情况下,我们不使用线程同步工具, 我们会出现,线程之间会互相抢夺,临界区的资源,造成数据不符合我们预期的结果, 后面再说解决办法,那么我们怎么帮助实现原子性 1 屏蔽中断,不让线程之间切换,让它完成再切换 2 底层硬…

Android CalendarView助你打造精美的Android日历应用

Android CalendarView助你打造精美的Android日历应用 1. 引言 移动应用中的日历功能对于用户来说至关重要&#xff0c;它不仅是时间管理的工具&#xff0c;还能帮助用户记录重要事件和安排活动。因此&#xff0c;一个高效、易用的日历控件对于移动应用的成功至关重要。 传统…

PaddlePaddle与OpenMMLab

产品全景_飞桨产品-飞桨PaddlePaddle OpenMMLab算法应用平台

windows平台安装labelme

之前写过一篇文章也是关于在windows平台安装labelme的&#xff1a;《windows平台python版labelme安装与使用_labelme下载-CSDN博客》&#xff0c;随着软件与工具的更新换代&#xff0c;按照同样的方法最近在使用的时候出现了错误&#xff0c;出现创建虚拟环境失败&#xff0c;具…

运维的利器–监控–zabbix–第二步:建设–部署zabbix agent--windows server系统--agent客户端安装部署

第一步&#xff1a;下载windows agent软件 第一点&#xff1a;zabbix官网针对linux和window系统有两种不同的安装方式&#xff0c;其中&#xff1a;windows为tar压缩包&#xff0c;根据你zabbix server安装的版本&#xff0c;在官网下载同样版本的agent软件。 amd64&#xff…

漂亮自适应APP下载页源码

漂亮自适应APP下载页源码,源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面 漂亮自适应APP下载页源码

公链系统开发全指南: 从规划到实施

在区块链技术的迅速发展和应用推广下&#xff0c;公链系统的开发成为了当前数字资产领域的热门话题。从规划到实施&#xff0c;公链系统的开发过程需要经历多个步骤&#xff0c;下文将详细介绍每个步骤。 第一步: 规划和设计 市场调研: 分析市场需求和竞争情况&#xff0c;确定…

preg_match详解(反向引用和捕获组)

在讲preg_match函数之前&#xff0c;我们先了解一下什么是php可变变量 php可变变量 在PHP中双引号包裹的字符串中可以解析变量&#xff0c;而单引号则不行 也就是在php中&#xff0c;双引号里面如果包含有变量&#xff0c;php解释器会将其替换为变量解释后的结果&#xff1b…

数据结构-链表练习(面试题)

1&#xff0c;翻转一个单链表 建立变量cur指向第二个节点&#xff0c;curN指向cur.next&#xff0c;将第二个节点的next改为head&#xff0c;headcur这样实现&#xff0c;前两个节点顺序的翻转&#xff0c;第二个节点指向了第一个节点&#xff0c;之后cur向后移&#xff08;cu…

Git中单独的功能特性分支是什么含义

在Git中&#xff0c;一个"功能特性分支"&#xff08;通常简称为“特性分支”&#xff09;是指从主开发分支&#xff08;比如main或master&#xff09;独立出来的分支&#xff0c;专门用于开发一个新功能、修复一个bug&#xff0c;或者进行实验性的尝试。使用特性分支…

多用户商城思维导图

订单优惠逻辑计算 以上是下面功能结构图中的部分流程&#xff1a;