0141.md

141. Linked List Cycle

Level:

Topic:

Similar Problem:

• 142. Linked List Cycle II

Question

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

Input: head = [3,2,0,-4], pos = 1
Output: true

Intuition

Use a slow and fast pointer

• if they meet each, there exists a cycle
• otherwise, false

Code

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

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast)
            return true;
    }

    return false;
}