My Java Solution With Picture Explanation


  • 0
    S
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            /**
             * head ---A---> start ----B---> meet ---|
             *                 ^                     |
             *                 |                     | 
             *                 |----------N----------|
             * slow: A + B
             * fast: A + B + N = 2 * slow = 2A + 2B
             * 
             * so: N = A + B
             * 
             * head to start : A + B
             * slow to start = meet to start = N = A + B
             */
            
            ListNode slow = head;
            ListNode fast = head;
            boolean hasCycle = false;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
                if(slow == fast){
                    hasCycle = true;
                    break;
                }
            }
            if(hasCycle){
                ListNode res = head;
                while(res != slow){
                    slow = slow.next;
                    res = res.next;
                }
                return res;
            }
            return null;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.