Leetcode 142 环形链表II（链表：快2慢1指针相遇即有环）

链表II（链表：快2慢1指针相遇即有环）"/>

Leetcode 142 环形链表II（链表：快2慢1指针相遇即有环）

Leetcode 142 环形链表II（链表：快2慢1指针相遇即有环）

• • 解法1

解法1

🔴1.【有无环】快慢指针，快指针每次走两步，慢指针每次走一步，若相遇（ fast = slow）则说明有环
// 快2慢1指针，开始俩人跑啊跑，快的走的快，慢的走的慢
// 之后快的先进环，慢的后进环
// 如果有环的话，那么在环里快的一定可以追上慢的
// 即：【追上即有环，追不上就木有】

🔴2.【在哪里是环的入口】之后数学推导可知入口索引x = (n-1)(y+z) + z，即让index1 = head，index2 = fast = slow，这两个相遇时的index1= index2 = x，即为所求

时间复杂度O(N)
其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)。

空间复杂度O(1)

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// fast每次走两步，slow每次走一步while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;// // 如果fast和slow可以相遇则说明有环if(fast == slow){// 寻找入口位置即返回x ，x = (n-1)(y+z) + z// 即再让index1 和 index2 相遇ListNode index1 = head;ListNode index2 = slow;while(index1 != index2){index1 = index1.next;index2 = index2.next;} return index1;}}return null; }
}