Leetcode刷题100天—141.环形链表（链表）—day01

偏执的太偏执、 2022-08-29 10:07 149阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]

### 题目:给定一个链表，判断链表中是否有环。 ###

*  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 `pos`来表示**链表尾连接到链表中的位置**（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：`pos`**不作为参数进行传递**，仅仅是为了标识链表的实际情况。
 *  如果链表中存在**环**，则返回 **true** 。 否则，返回 **false** 。
 *  **进阶**：你能用 O(1)（即，常量）**内存解决**此问题吗？  
    **示例 1**：  
    ![在这里插入图片描述][224b9f4402804bfbbe8f44fd93669431.png]

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

**示例 2：**  
![在这里插入图片描述][c51b780ace174dc0a3663882af695cd0.png]

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

**示例 3：**  
![在这里插入图片描述][4257dd97ec774636934a1a97df801b43.png]

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

**提示：**

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

### 代码 ###

package 链表;
    /* * https://leetcode-cn.com/problems/linked-list-cycle/ * 给定一个链表，判断链表中是否有环。如果链表中存在环，则返回 true 。 否则，返回 false 。 * 快慢指针思想，比如慢指针会走一步，快指针会走两步 * 复杂度:首先看数据规模，大概是o(n) */
    public class _141_环形链表 { 
    	public boolean hasCycle(ListNode head) { 
    	        if(head==null || head.next==null) { 
    	        	return false;
    	        }
    // 慢指针
    	        ListNode show=head;
    // 快指针
    	        ListNode fast=head.next;
    // 如何终止while循环？如果不是环形说明fast最后为null
    	        while (fast!=null && fast.next!=null) { 
    	        	show=show.next;
    // 快指针走两步 
    	        	fast=fast.next.next;
    // 如果快慢指针相等就说明是环形
    	        	if (show==fast) return true;
    	        }
    	        return false;
    	    }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]: /images/20220829/4e93aa29460c40f2a7c8db8810646c1e.png
[224b9f4402804bfbbe8f44fd93669431.png]: /images/20220829/ba966ac2e43640278ba775dadbd9ebf7.png
[c51b780ace174dc0a3663882af695cd0.png]: /images/20220829/c9c790e36bdc4618a5d5c61afa5fc7a2.png
[4257dd97ec774636934a1a97df801b43.png]: /images/20220829/fc8a7ba03b194023861c49a211f46d45.png