数据结构(Java版)第八期:LinkedList与链表(三)

server/2025/1/16 16:43:00/

专栏:数据结构(Java版)

个人主页:手握风云

目录

一、链表中的经典面试题

1.1. 链表分割

1.2. 链表的回文结构

1.3. 相交链表

1.4. 环形链表


一、链表中的经典面试题

1.1. 链表分割

        题目中要求不能改变原来的数据顺序,也就是如上图所示。我们先定义一个cur引用去遍历这个链表,用每个结点的val值与x进行比较,然后利用尾插的方法把结点插入进两个链表中。我们先定义bs、be、as、ae四个引用来表示两个链表的头尾,在尾插的时候需要注意,利用ae.next = node;ae = node,记录下尾结点,保证ae永远指向最后一个结点,同时be.next=as,连接上两个链表

java">class ListNode{int val;ListNode next = null;public ListNode(int val) {this.val = val;}
}public class Partition {public ListNode partition(ListNode pHead, int x){ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;while(cur != null){if(cur.val < x){}else{}}}
}

        代码的大体框架已经写好,这时我们需要考虑一下当第一段插入第一个节点时,第一个节点既是头又是尾。这时有需要分两种情况,第一次插入与下一次插入,来移动be引用。

java">        while(cur != null){if(cur.val < x){//第一次插入if(bs == null){be = bs = cur;}else {be.next = cur;be = cur;}}else{//第一次插入if(as == null){ae = as = cur;}else {ae.next = cur;ae = cur;}}cur = cur.next;

       这时的代码还存在一种我们没有想到的情况,如果给定的测试用例都大于x的值呢。这是我们就需要返回as。我们还需要分情况。

java">        if(bs == null){return as;}

       如果这是我们放到OJ进行测试,发现报出异常。

        这个异常的原因比较隐蔽。因为bs为空,尾节点ae会返回bs,如果ae之前的地址指向之前的某个节点,就会造成链表的死循环,此时我们要将排列之后的链表最后一个节点手动置为null。

完整代码: 

java">class ListNode{int val;ListNode next = null;public ListNode(int val) {this.val = val;}
}public class Partition {public ListNode partition(ListNode pHead, int x){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 = cur;}}else{//第一次插入if(as == null){ae = as = cur;}else {ae.next = cur;ae = cur;}}cur = cur.next;}if(bs == null){return as;}be.next = as;//连接上两个链表if(as != null){ae.next = null;}return bs;}
}

1.2. 链表的回文结构

       第一种思路,我们可以使用双引用算法,一个left引用从左开始向右移动,另一个right引用从右开始向左移动。但由于这个链表是单链表,只能从一个方向遍历。

       第二种思路,把链表里的val值取出,存进一个数组中,但题目要求空间复杂度为O(n) 。

       第三种思路,翻转一半的链表。过程分为三步,第一步,找到链表的中间部分;第二步,将链表的一半进行翻转。我们在上一期中,已经实现了翻转链表和寻找链表的中间节点。

java">while(cur != null){curN = cur.next;cur.next = slow;slow = cur;cur = curN;
}

        利用上面的代码我们就可以来翻转链表,第三步,head从前往后,slow从后往前,比较head.val是否与slow.val相等,直到slow引用与头节点相遇为止。这里我们讨论的是奇数个节点的链表,如果是有偶数个节点的链表,那么fast为空。

       当链表的节点为偶数时,我们不能按照之前的做法,当head.next = slow时,直接返回true。

完整代码:

java">import java.util.Scanner;class ListNode{int val;ListNode next;public ListNode(int val) {this.val = val;}
}public class PalindromeList {public boolean chkPalindrome(ListNode A){//1、找到链表的中间节点ListNode fast = A;ListNode slow = A;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、引用A与slow同时移动while(A != slow){if(A.val != slow.val){return false;}//判断偶数个节点情况if(A.next == slow){return true;}A = A.next;slow = slow.next;}return true;}
}

1.3. 相交链表

       对于链表相交的问题,我们首先要考虑明白,到底是X形相交,还是Y形相交?

       如上图所示,很明显两个链表相交之后呈Y形。要解决问题,我们同样利用双引用的算法。第一步,先求出两个链表的长度len1、len2;第二步求出两个链表的长度差len=len1-len2;第三步,让长的链表先走len步;第四步,headA与headA同时走,相遇之后就是公共交节点。

      这个题的思路其实很简单,但是其中也有一些比较麻烦的步骤。在第二步中,如果说len1<len2,那么len<0。第三步中,我们又怎么知道哪个链表更长?

java">class ListNode{int val;ListNode next;ListNode(int x){val = x;next = null;}
}public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB){ListNode pl = headA;//先假设链表A是长的ListNode ps = headB;//求两个链表的长度int len1 = 0,len2 = 0;while(pl != null){len1++;pl = pl.next;}while(ps != null){len2++;ps = ps.next;}pl = headA;ps = headB;//求链表的长度差int len = len1 - len2;if(len < 0){pl = headB;ps = headA;len = len2-len1;}//让pl先走len步while(len != 0){pl = pl.next;len--;}//pl与ps同时走,知道相遇。while(pl != ps){pl = pl.next;ps = ps.next;}//如果没有公共节点,直接返回nullif(pl == null){return null;}return pl;}
}

1.4. 环形链表

        快慢引用,即慢引用⼀次⾛⼀步,快引用⼀次⾛两步,两个引用从链表起始位置开始运⾏,如果链表带环则⼀定会在环中相遇,否则快引用率先⾛到链表的末尾。与现实生活中不同,两人相遇有可能是擦肩而过。而引用确实一步一步走的。

        为什么要让快引用走两步,慢引用走一步呢?我们想象一种最极限的情况,当fast刚走完一圈时,slow刚进入环内,两个引用的距离差刚好是一个环的距离。当fast与slow每走一次,它们的距离就越接近一个环。

java">class ListNode{int val;ListNode next;ListNode(int x){val = x;next = null;}
}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;}
}


http://www.ppmy.cn/server/158865.html

相关文章

线程池底部工作原理

线程池内部是通过线程和队列实现的&#xff0c;当我们通过线程池处理任务时&#xff1a; 如果线程池中的线程数量小于corePoolSize&#xff0c;无论是否有处于空闲的线程&#xff0c;都创建新的线程来处理被添加的任务。 如果线程池中的线程数量等于corePoolSize&#xff0c;…

centos安装golang

1.下载golang golang所有版本网址 https://studygolang.com/dl //下载并解压到/usr/local文件下 wget https://studygolang.com/dl/golang/go1.18.3.linux-amd64.tar.gz //解压并复制到/user/local文件夹下 tar -C /usr/local -zxf go1.18.3.linux-amd64.tar.gz 2.编辑环境变…

SQL正则表达式用法大全以及如何利用正则表达式处理复杂数据

正则表达式用法大全 在SQL中&#xff0c;正则表达式通常用于模式匹配&#xff0c;以便搜索、替换或验证数据。不同的SQL数据库管理系统&#xff08;DBMS&#xff09;支持不同的正则表达式功能。以下是常见的SQL中正则表达式的用法和相关功能&#xff1a; 1. MySQL 正则表达式 …

unity——Preject3——UI管理器

目录 1.canvas Canvas 的主要功能 Canvas 的组件 Canvas 的渲染模式 Canvas 的使用步骤 Match 的作用 Match 的工作原理 如何选择合适的 Match 值 示例 总结 EventSystem 的作用 EventSystem 和 Canvas 的关系 EventSystem 的组件 EventSystem 的工作流程 2.代码…

ffmpeg视频总帧数获取,取某一帧的图像方法

FFmpeg的Static版本的bin文件夹中只有三个.exe文件&#xff0c;分别是&#xff1a;ffmpeg.exe&#xff0c;ffplay.exe和ffprobe.exe&#xff0c;各功能如下&#xff1a; ffmpeg.exe&#xff1a;音视频转码、转换器 ffplay.exe&#xff1a;简单的音视频播放器 ffprobe.exe&am…

【数据结构-堆】力扣1792. 最大平均通过率

一所学校里有一些班级&#xff0c;每个班级里有一些学生&#xff0c;现在每个班都会进行一场期末考试。给你一个二维数组 classes &#xff0c;其中 classes[i] [passi, totali] &#xff0c;表示你提前知道了第 i 个班级总共有 totali 个学生&#xff0c;其中只有 passi 个学…

qBittorent访问webui时提示unauthorized解决方法

现象描述 QNAP使用Container Station运行容器&#xff0c;使用Docker封装qBittorrent时&#xff0c;访问IP:PORT的方式后无法访问到webui&#xff0c;而是提示unauthorized&#xff0c;如图&#xff1a; 原因分析 此时通常是由于设备IP与qBittorrent的ip地址不在同一个网段导致…

【汇编】汇编编程中的指令传参方式

1. 指令传参方式 汇编指令传参有2种方式。 第一种是常见的 操作数传参&#xff0c;如&#xff1a; move ax, bx第二种是&#xff0c;绑定寄存器传参。有的指令在调用时&#xff0c;虽然不需要操作数&#xff0c;但是它会默认使用某几个寄存器&#xff0c;调用时需要提前将寄…