(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;
    }
}


相关文章
|
2月前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
1月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
23 3
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
40 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
46 0
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
04_两两交换链表中的节点
04_两两交换链表中的节点
|
3月前
|
存储 Java
|
3月前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
101 0
|
3月前
|
存储 Java
【Java集合类面试十】、HashMap中的循环链表是如何产生的?
在多线程环境下,HashMap在扩容时如果发生条件竞争,元素的插入顺序可能形成循环链表,导致死循环。