Java: Linked List Cycle II

Thought Process

To detect the starting node of a cycle in a linked list, we use Floyd's Tortoise and Hare algorithm. First, we determine if a cycle exists by using a slow pointer and a fast pointer. If they meet, a cycle is confirmed. Then, we reset a entry pointer to the head and move both the entry pointer and the slow pointer one step at a time until they meet. The meeting point is the starting node of the cycle. 

/**
 * 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) {

        ListNode slow = head;
        ListNode fast = head;
        ListNode entry = head;

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){

                while(slow != entry){
                    slow = slow.next;
                    entry = entry.next;
                }
                return entry;
            }
        }
        return null;
        
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the linked list once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses only three pointers, ensuring constant space usage.

Code copied!