LeetCode 141: Linked List Cycle

Explanation

To determine if a linked list has a cycle, we can use the "fast and slow pointers" approach. We initialize two pointers, slow and fast, both pointing to the head of the linked list. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. If there is a cycle in the linked list, the fast pointer will eventually meet the slow pointer. If there is no cycle, the fast pointer will reach the end of the list (null) before the slow pointer.

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the linked list.

Space Complexity

The space complexity of this approach is O(1) as we are using only two extra pointers.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == 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;
    }
}