Linked List Cycle

Leetcode Problem: Linked List Cycle

Objective:

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Pattern: Two Pointer Technique

Approach:

1. Edge case: If input is null then the list is empty so a cycle does not exist.
2. Create two pointers both starting at head. One pointer moving at a slow pace, while the other pointer moves at twice the speed.
3. If the slower pointer ends up catching up to the faster pointer then return true because there is a cycle.
4. If the faster pointer reaches a null then return false because there is no cycle.

Big-O Notation:

Time Complexity: O(n)
We have iterate n times for each element.

Space Complexity: O(1)
We do not use any additional data structures for storage.

Code:

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null){
            return false;
        }

        ListNode slow = head; 
        ListNode fast = head;

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

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

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}