Linked List Cycle

Floyd’s Cycle Finding Algorithm

https://leetcode.com/problems/linked-list-cycle/description/

Given head, the head of a linked list, determine if the linked list has a cycle in it.

1. Initialize Two Pointers:
   • Create two pointers, slow and fast, and set slow to the head of the linked list and fast to the next of the head.
2. Traverse the Linked List:
   • Start a loop where the slow pointer moves one step at a time, and the fast pointer moves two steps at a time.
3. Check for a Cycle:
   • In each iteration, check if the slow and fast pointers meet. If they do, it indicates the presence of a cycle in the linked list.
4. Termination Conditions:
   • If the fast pointer reaches the end of the linked list (i.e., fast or fast.next is None), there is no cycle, and the algorithm terminates.
5. Return Result:
   • If a cycle is found, return True. Otherwise, return False.

public boolean hasCycle(ListNode head) {
        if(head == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

Time Complexity: O(n)
Space Complexity: O(1)

https://leetcode.com/problems/linked-list-cycle-ii/description/

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

 public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = head;
        fast = fast.next;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }