package com.striner.java.test;

public class HasCycle141 {

//141. 环形链表

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

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

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

//

//进阶：

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

//

//示例 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 或者链表中的一个 有效索引 。

//

//https://leetcode-cn.com/problems/linked-list-cycle/

public static void main(String[] args) {

ListNode141 n1 = new ListNode141(3);

ListNode141 n2 = new ListNode141(2);

ListNode141 n3 = new ListNode141(0);

ListNode141 n4 = new ListNode141(-4);

n1.next = n2;

n2.next = n3;

n3.next = n4;

n4.next = n2;

HasCycle141 hasCycle = new HasCycle141();

System.out.println(hasCycle.hasCycle(n1));

}

public boolean hasCycle(ListNode141 head) {

if (head == null || head.next == null) return false;

ListNode141 temp1 = head;

ListNode141 temp2 = head;

while(true) {

if (temp2 == null || temp2.next == null) return false;

temp1 = temp1.next;

temp2 = temp2.next.next;

if (temp1 == temp2) return true;

}

}

}

class ListNode141 {

int val;

ListNode141 next;

ListNode141(int x) {

val = x;

next = null;

}

}

//执行结果： 通过

//显示详情

//执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户

//内存消耗： 39.8 MB , 在所有 Java 提交中击败了 11.17% 的用户