題目142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
思路:是否存在環(huán),環(huán)開始的位置,以及環(huán)的長度以及證明,參見LeetCode單鏈表(LinkList)總結(jié)
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
ListNode lowerNode = head;
ListNode fastNode = head;
while(lowerNode != null && fastNode != null){
if(fastNode.next == null){
return null;
}
fastNode = fastNode.next.next;
lowerNode = lowerNode.next;
if(lowerNode == fastNode){
fastNode = head;
while(lowerNode != fastNode){
lowerNode = lowerNode.next;
fastNode = fastNode.next;
}
return lowerNode;
}
}
return null;
}
}
