Problem Description

Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.

There is a cycle in a linked list if at least one node in the list can be visited again by following the next pointer.

Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set its next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.

Note: index is not given to you as a parameter.

Example 1:

Input: head = [1,2,3,4], index = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], index = -1
Output: false

Constraints:

• 0 <= Length of the list <= 1000
• -1000 <= Node.val <= 1000
• index is -1 or a valid index in the linked list.

Approach

We can use Floyd’s Cycle-Finding Algorithm, also known as the “tortoise and hare” approach. We initialize two pointers, a slow pointer (s) and a fast pointer (c), both pointing to the head of the list. We move the slow pointer one step at a time and the fast pointer two steps at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer, and they will point to the same node. If the fast pointer reaches the end of the list (null), it means there is no cycle.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode c = head;
        ListNode s = head;
        while (c != null && c.next != null) {
            c = c.next.next;
            s = s.next;
            if (c == s) {
                return true;
            }
        }
        return false;
    }
}