題目

給定一個鏈表的頭節點 ?head?，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。

如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環。注意：pos?不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改?鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例?2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。

題解

/*** 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) {//設環外的部分為a,環入口到相遇點（正向）為b,環長為b+c//fast:a+b+n(b+c) slow:a+b 2(a+b)=a+b+n(b+c) a=c+(n-1)(b+c)//slow按照環的方向走到入口與head走到入口的距離相等//slow一定在第一圈內與fast相遇 //如果slow剛進入環，slow與fast相差N步，則一共執行fast兩步slow一步的循環N次//也就是slow走了N步，而N小于環長ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {while (head != slow) {slow = slow.next;head = head.next;}return slow;}}return null;}
}