(Java)链表OJ题(环形链表,判断链表是否带环,求入环的第一个节点)

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

1.判断链表是否带环

环形链表


题目:


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


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


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


image.png


⭐思路:采用快慢指针的方法,快指针一次走两步,慢指针一次走一步,如果链表带环的话,两个指针将会在环中相遇,如果不带环,快指针将会先到达链表的末尾。


👁‍🗨参考代码:

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;            //快指针优先到达链表末尾,说明不带环    
    }
}


🤔思考:


1. 为什么快指针一次走两步,慢指针一次走一步可以?


因为,如果链表带环,快指针先进入环,慢指针后进入环,快指针每次比慢指针多走一步,在环中两个指针的距离每次减少一步,直到距离为0,所以这种走法可以。


2. 快指针一次走3步,4步......n步可以吗?


假设快指针走3步,慢指针走1步,快指针优先进入环,慢指针后进入环,看如下情况:

image.png



🍊 也就是说只有快指针一次走2步,慢指针一次走1步,才能在任何情况下都能相遇,其他走法或多或少会出点问题。


2.返回带环链表的第一个入环结点

环形链表Ⅱ


题目:


给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。


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


不允许修改 链表。  示例:

image.png



🤔思路:这里记住一个结论:让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个 指针都是每次均走一步,最终肯定会在入口点的位置相遇。


⭐证明过程:

image.png



对此图进行说明:H为链表起始点,E为入环点,M为判环时相遇点


设:环的长度为R,H到E的距离为L,E到M的距离为X,则M到E的距离为R-X


判环时快慢指针所走的长度:


fast:L+X+nR            slow:L+X


注意:


1. 当慢指针进入环时,快指针可能已经在环中走了n圈了


2. 慢指针进入环时,快指针肯定会在慢指针走一圈之内追上慢指针


快指针的速度为慢指针的两倍,则有如下关系:


2*(L+X) = L+X+nR


L+X = nR


L = nR - X(n为1,2,3,4......n的大小取决于环的大小,环越小,n越大)


极端情况下,假设n=1,此时:L = R - X ,即:一个指针从链表起始位置开始走,一个指针从判环相遇点环绕,每次都走一步,最终两个指针会在环的入口点相遇


👁‍🗨参考代码:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //判断链表是否带环
        ListNode fast = head;
        ListNode slow = head;
        Boolean isCircle = false;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                isCircle = true;
                break;
            }
        }
        if(isCircle == false){
            return null;
        }
        //链表带环,求入环的第一个节点
        ListNode pH = head;   //链表头
        ListNode pM = fast;   //判环相遇点
        while(pH != pM){
            pH = pH.next;
            pM = pM.next;
        }
        return pH;
    }
}


相关文章
|
23天前
|
分布式计算 资源调度 Hadoop
大数据-01-基础环境搭建 超详细 Hadoop Java 环境变量 3节点云服务器 2C4G XML 集群配置 HDFS Yarn MapRedece
大数据-01-基础环境搭建 超详细 Hadoop Java 环境变量 3节点云服务器 2C4G XML 集群配置 HDFS Yarn MapRedece
57 4
|
21天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
13 0
LeetCode第二十四题(两两交换链表中的节点)
|
21天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
36 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
22天前
|
分布式计算 Java Hadoop
Hadoop-30 ZooKeeper集群 JavaAPI 客户端 POM Java操作ZK 监听节点 监听数据变化 创建节点 删除节点
Hadoop-30 ZooKeeper集群 JavaAPI 客户端 POM Java操作ZK 监听节点 监听数据变化 创建节点 删除节点
50 1
|
14天前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
28 0
|
25天前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
22 0
|
3月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
04_两两交换链表中的节点
04_两两交换链表中的节点
|
4月前
【数据结构OJ题】环形链表
力扣题目——环形链表
36 3
【数据结构OJ题】环形链表