链表是否有环，以及环的位置

水深无声 2023-02-08 12:46 29阅读 0赞

介绍两道算法题，与环形链表有关。

*  [LeetCode 141. Linked List Cycle（Easy）][LeetCode 141. Linked List Cycle_Easy]
 *  [LeetCode 142. Linked List Cycle II（Medium）][LeetCode 142. Linked List Cycle II_Medium]

这两道题有相关性，第一道判断单链表是否有环，第二道是如果有环，找到成环的节点。

## 环形链表 ##

给定一个链表，判断链表中是否有环。

示例：

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

输入：head = [3,2,0,-4] 
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

### 思路 ###

这道题有两个解法，哈希表和快慢指针

*  哈希集合：遍历链表，判断哈希表有没有当前的引用，如果有，就说明曾经遍历过，今儿又遍历到，于是返回true；否则存入当前节点的引用，继续遍历，直到为null。代码请看官方题解。
 *  快慢指针  
    定义两个指针，慢指针每次走一步，快指针每次走两步。  
    假如有环，慢指针和快指针肯定会相遇 。原因是，慢指针进入环之后，两者顺时针运动。想象一下，快指针距离慢指针有k个节点，快指针每次比慢指针多走一步，总有一天追上慢指针，此时相遇了，证明有环

### 代码实现 ###

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            if(head == null || head.next == null) {
        
                return false;
            }
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
        
                    return true;
                }
            }
            return false;
        }
    }

## 环形链表（找到环的位置） ##

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。  
示例  
![在这里插入图片描述][0f0f002fa52f4fbc90cb088b23f78e64.png]

输入：head = [3,2,0,-4]
    输出：返回值为2的引用
    解释：链表中有一个环，其尾部连接到第二个节点。

### 思路 ###

这道题有两个解法，哈希表和快慢指针

*  哈希集合：遍历链表，判断哈希表有没有当前的引用，如果有，就说明曾经遍历过，今儿又遍历到，于是返回该引用；否则存入当前节点的引用，继续遍历，直到为null。代码请看官方题解。
 *  快慢指针  
    定义两个指针，慢指针每次走一步，快指针每次走两步。  
    假如有环，慢指针和快指针肯定会相遇 。相遇时，新开一个指针 q，从 head 出发，每次走一步，当 q = slow，即它们相遇时，**相遇点肯定是环上相连的节点**，返回该节点即可。

### 代码实现 ###

/**
     * 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) {
        
            if(head == null || head.next == null) {
        
                return null;
            }
            ListNode fast = head, slow = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
        
                    // 快慢相遇，新起一个指针，从头结点出发
                    ListNode q = head;
                    while (q != slow) {
        
                        // 每次走一步
                        q = q.next;
                        slow = slow.next;
                    }
                    return slow;
                }
            }
            // 无环，返回null
            return null;
        }
    }

这里遗留了一个证明，q 和 slow 为什么一定在环点相遇？  
具体看这篇证明

[经典面试题：环形链表的判断与定位][Link 1]

本篇完

[LeetCode 141. Linked List Cycle_Easy]: https://leetcode-cn.com/problems/linked-list-cycle/
[LeetCode 142. Linked List Cycle II_Medium]: https://leetcode-cn.com/problems/linked-list-cycle-ii/submissions/
[99af37f98c534a2794e8f9a83eca36cc.png]: /images/20230208/153136c6e2d5419d86639062909063e3.png
[0f0f002fa52f4fbc90cb088b23f78e64.png]: /images/20230208/d0c8b86195634c85bad0a77ad8f89e46.png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/107947773