单链表判断是否有环,并返回环的入口结点——java实现

小咪咪 2024-03-17 10:51 84阅读 0赞

## 单链表判断是否有环,并返回环的入口结点 ##

### 题目1 ###

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

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

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

![在这里插入图片描述][6c58bbc3337347c38d2224213d34d4d3.png]  
原题OJ 链接  
https://leetcode.cn/problems/linked-list-cycle/submissions/

**解答**

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            ListNode slow = head;
            ListNode fast = head;
            while(fast != null && fast.next != null){
        
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
        
                    return true;
                }
            }
            return false;
        }
    }

### 题目2 ###

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。  
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。  
不允许修改 链表。

![在这里插入图片描述][b3bf1fb035f44f58ac89ad4f34003618.png]

**解答**  
![在这里插入图片描述][4b3250e4721d4b258b7f86793515f162.png]（图片引用自比特鹏哥）

**让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇**

**解答**

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode ret = hasCycle(head);
            ListNode pre = head;
            if(ret == null){
        
                return null;
            }
            while(pre != ret){
        
                pre = pre.next;
                ret = ret.next;
            }
            return pre;
            
    
        }
        public ListNode hasCycle(ListNode head) {
        
            ListNode slow = head;
            ListNode fast = head;
            while(fast != null && fast.next != null){
        
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
        
                    return fast;
                }
            }
            return null;
        }
    }

[6c58bbc3337347c38d2224213d34d4d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/5fb7dd578a9145cf8772a12d5e041d93.png
[b3bf1fb035f44f58ac89ad4f34003618.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/5c3e714666d44d53ab8bd14a504b9896.png
[4b3250e4721d4b258b7f86793515f162.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/cd4f09b3316f4dba89b89510359ab175.png