package com.striner.java.test01;

public class DetectCycle142 {

//142. 环形链表 II

//给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

//

//为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

//

//说明：不允许修改给定的链表。

//

//进阶：

//

//你是否可以使用 O(1) 空间解决此题？

//

//

//示例 1：

//

//

//

//输入：head = [3,2,0,-4], pos = 1

//输出：返回索引为 1 的链表节点

//解释：链表中有一个环，其尾部连接到第二个节点。

//示例 2：

//

//

//

//输入：head = [1,2], pos = 0

//输出：返回索引为 0 的链表节点

//解释：链表中有一个环，其尾部连接到第一个节点。

//示例 3：

//

//

//

//输入：head = [1], pos = -1

//输出：返回 null

//解释：链表中没有环。

//

//

//提示：

//

//链表中节点的数目范围在范围 [0, 104] 内

//-105 <= Node.val <= 105

//pos 的值为 -1 或者链表中的一个有效索引

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

public static void main(String[] args) {

// head = [3,2,0,-4], pos = 1

ListNode142 node1 = new ListNode142(3);

ListNode142 node2 = new ListNode142(2);

ListNode142 node3 = new ListNode142(0);

ListNode142 node4 = new ListNode142(-4);

node1.next = node2;

node2.next = node3;

node3.next = node4;

node4.next = node2;

DetectCycle142 detectCycle = new DetectCycle142();

ListNode142 node = detectCycle.detectCycle(node1);

System.out.println(node == null ? null : node.val);

}

public ListNode142 detectCycle(ListNode142 head) {

if (head == null) return null;

ListNode142 fastIndex = head;

ListNode142 slowIndex = head;

boolean isCycle = false;

while (fastIndex.next != null && fastIndex.next.next != null) {

slowIndex = slowIndex.next;

fastIndex = fastIndex.next.next;

if (slowIndex == fastIndex) {

isCycle = true;

break;

}

}

if (isCycle) {

while(head != fastIndex) {

head = head.next;

fastIndex = fastIndex.next;

}

} else {

return null;

}

return head;

}

}

class ListNode142 {

int val;

ListNode142 next;

ListNode142(int x) {

val = x;

next = null;

}

}

//执行结果： 通过

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

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