142. 環(huán)形鏈表 II
問題
給定一個(gè)鏈表高镐，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)畸冲。 如果鏈表無環(huán)，則返回 null算行。
為了表示給定鏈表中的環(huán)苫耸，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1量淌，則在該鏈表中沒有環(huán)。
說明：不允許修改給定的鏈表叙身。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個(gè)環(huán)硫狞，其尾部連接到第二個(gè)節(jié)點(diǎn)晃痴。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個(gè)環(huán)泣侮，其尾部連接到第一個(gè)節(jié)點(diǎn)紧唱。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)。
進(jìn)階：
你是否可以不用額外空間解決此題蛹锰？
解法
我們?cè)诃h(huán)形鏈表的問題中知道铜犬，可以使用快慢指針來判斷一個(gè)鏈表是不是有環(huán)癣猾。但是該題目是需要返回鏈表的入環(huán)節(jié)點(diǎn)，僅使用快慢指針只是判斷出了是否有環(huán)纷宇，所以還需要進(jìn)一步的邏輯才能獲取到入環(huán)節(jié)點(diǎn)蛾方。
假設(shè)鏈表有環(huán)，設(shè)入環(huán)點(diǎn)的為,從
到
的距離為
,設(shè)快慢指針相交點(diǎn)為
,從
到
的距離為
,此時(shí)可得作岖，慢指針走過的距離為
五芝，同時(shí)，我們知道快指針走過的距離是慢指針的一倍沉删，即
，此時(shí)可得如下結(jié)論砖茸，
- 慢指針再走
得距離就回到
點(diǎn)
- 慢指針再走
的距離就到了
點(diǎn)
第一點(diǎn)對(duì)我們解本題沒有什么用凉夯，看第二點(diǎn)，我們?cè)谝婚_始定義的到入環(huán)點(diǎn)
代碼
java實(shí)現(xiàn)
/**
* 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) {
if (head == null || head.next == null) {
return null;
}
//使用快慢指針的方式進(jìn)行
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
//此時(shí)說明有環(huán)，需要處理
fast = head;
while(true) {
if (slow == fast) {
return slow;
}
slow = slow.next;
fast = fast.next;
}
}
}
//無環(huán)狀態(tài)
return null;
}
}
