描述
給定一個鏈表笼痛，如果鏈表中存在環(huán)膳汪，則返回到鏈表中環(huán)的起始節(jié)點的值，如果沒有環(huán)操软，返回 null。
樣例
給出 -21->10->4->5, tail connects to node index 1宪祥，返回 10
代碼實現(xiàn)
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode fast = head.next;
ListNode slow = head;
while (fast != slow) {
if (fast == null || fast.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
/**while (head != fast.next) {
head = head.next;
slow = fast.next;
}**/
//用慢指針的next與head比較
while (head != slow.next) {
head = head.next;
slow = slow.next;
}
return head;
}
}
