常州微网站建设网络营销工程师

1.问题描述

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

        示例1

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

        示例2 

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

        示例3 

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

        提示

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 

        难度等级

               简单

        题目链接

                环形链表

2.解题思路

        这道环形链表的问题相当容易解决，有点像我们小学时候的追及问题。我们定义两个快慢指针来模拟两个人相互追及。

        //快指针ListNode fast = head;//慢指针ListNode slow = head;

        如果链表真的是环形链表的话，它就会形成一个圈，那么我们的快慢指针相当于两个人从同一个入口进入一个闭环的操场在跑步。快的那个人只要时间足够，就可以比慢的那个人多跑一圈而相遇。

        我们假设快指针的步频为2，慢指针步频为1，如果快指针能走到尽头，遇到null，说明不是环形链表，如果与慢指针相遇，说明是环形链表。

        //遍历while(fast != null && fast.next != null){//慢指针一次走一步slow = slow.next;//快指针一次走两步fast = fast.next.next;if(slow == fast){return true;}}return false;

3.代码展示

/*** 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 fast = head;//慢指针ListNode slow = head;//遍历while(fast != null && fast.next != null){//慢指针一次走一步slow = slow.next;//快指针一次走两步fast = fast.next.next;if(slow == fast){return true;}}return false;}
}

4.总结

        这道环形链表的题，我们当成小学的追及相遇问题就可以轻松解决了。祝大家刷题愉快~