142. Linked List Cycle II

题目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?

思路:是否存在环,环开始的位置,以及环的长度以及证明,参见LeetCode单链表(LinkList)总结

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;
    }
}