1.題目描述????????
????????給定一個鏈表的頭節點 ?head?，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。
如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環。注意：pos?不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。
不允許修改?鏈表。
提示：
- 鏈表中節點的數目范圍在范圍?
[0, 104]?內 -105 <= Node.val <= 105pos?的值為?-1?或者鏈表中的一個有效索引
2.解決思路
? ? ? ? 這道題目相比上一道題目，要求有一些變化，現在我們需要返回鏈表入環的點。所以上一道題的解法不能夠復用，因為我們并不知道他們在哪個位置相遇。
? ? ? ? 為了完成這道題目，可以這樣思考，因為首先要找到相遇點，所以不可避免我們還是要用到快慢指針，而解題的關鍵就是如何判斷相遇點的位置關系。
????????設鏈表中環外部分的長度為 a。slow 指針進入環后，又走了 b 的距離與 fast 相遇。此時，fast 指針已經走完了環的 n 圈，因此它走過的總距離為 a+n(b+c)+b=a+(n+1)b+nc。
，任意時刻，fast 指針走過的距離都為 slow 指針的 2 倍。因此，我們有
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a+(n+1)b+nc=2(a+b)?a=c+(n?1)(b+c)
有了 a=c+(n?1)(b+c) 的等量關系，我們會發現：從相遇點到入環點的距離加上 n?1 圈的環長，恰好等于從鏈表頭部到入環點的距離。
所以也就是：相遇點距離入環點的距離就等于頭結點距離入環點的距離
3.步驟講解
? ? ? ? 1.因為快指針的存在，先判斷鏈表長度，小于兩個節點則返回null
? ? ? ? 2.定義三個節點，同時指向頭結點，其中pre用于最后一步找入環點位置，其余兩個是快慢指針
? ? ? ? 3.進行循環，條件是遍歷不到空，也就是不為無環鏈表時進行循環。
? ? ? ? 4.先讓慢指針移動一步，然后判斷快指針的下一個節點是否為空，為空返回null，反之快指針移動兩個節點
? ? ? ? 5.當快慢指針相遇時，進行第二步操作，經過上述分析，可知此時讓指向頭結點的pre指針與慢指針slow同時開始移動，他們相遇的位置就是入環點。返回pre即可
4.代碼展示
class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public ListNode hasCycle(ListNode head) {if (head == null || head.next == null){return null;}ListNode pre = head;ListNode slow = head;ListNode fast = head;while (fast != null){slow = slow.next;if (fast.next != null){fast = fast.next.next;} else {return null;}if (slow == fast){while (pre != slow){pre = pre.next;slow = slow.next;}return pre;}}return null;}5.執行結果
在leetcode中測試用例平均耗時0ms
內存分布43.86MB
