141. 环形链表

系统管理员 2022-09-08 00:21 196阅读 0赞

[https://leetcode-cn.com/problems/linked-list-cycle/][https_leetcode-cn.com_problems_linked-list-cycle]

难度简单1177

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

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

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

**进阶：**

你能用 *O(1)*（即，常量）内存解决此问题吗？

**示例 1：**

![4a18acda10c1606aa5d1132b9de26d61.png][]

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

**示例 2：**

![1a6fcfc68d7340c39151075f7fa53150.png][]

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

**示例 3：**

![3039274e08a9385ea77b20a81060ed40.png][]

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

**提示：**

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

通过次数497,356提交次数971,032

/**
     * 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) {
            int flag = 100005;
            while(head!=null)
            {
                if(head.val ==flag) return true;
                head.val = flag;
                head = head.next;
            }
            return false;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_18_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_linked-list-cycle]: https://leetcode-cn.com/problems/linked-list-cycle/
[4a18acda10c1606aa5d1132b9de26d61.png]: /images/20220829/a401977d2e834698b0fcc767c16ac52b.png
[1a6fcfc68d7340c39151075f7fa53150.png]: /images/20220829/6133362961cb41c19e060b5f138cff92.png
[3039274e08a9385ea77b20a81060ed40.png]: /images/20220829/7cae2e36be4a49f0955564ec5a892303.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/35b56fb320af496bb4d3698d1d8b5027.png