O(n) Time and O(1) Space Java Solution with Explanation


  • 0
    /**
     * 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 || head.next.next == null) return null;
            
            ListNode slow = head.next;
            ListNode fast = head.next.next;
            
            // Let A be the distance to the start of the cycle.
            // Let B be the distance from the start of the cycle to the intersection of fast and slow.
            // Let C be the length of the cycle.
            // A + B + C = 2A + 2B. This is because by the time intersection occurs, the fast pointer has already performed a cycle.
            // Therefore C = A + B.
            while (slow != fast) {
                if (fast == null || fast.next == null) return null;
                slow = slow.next;
                fast = fast.next.next;
            }
            
            // From the slow / fast pointer's current location we just need to travel A to reach the start of the cycle.
            // How do we find A? Just start another pointer from the head and see when the slow pointer and this pointer meet.
            while (head != slow) {
                head = head.next;
                slow = slow.next;
            }
            
            return head;
        }
    }
    

Log in to reply
 

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