3. Linked List Cycle

Description

Linked List Cycle
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.

Example 1:

Input: head = [3,2,0,-4], pos = 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], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Approach - Floyd’s tortoise and hare

Slow and fast pointer - keeping moving forward if we have a loop they would meet somewhere before fast reaches null
Time:O(n) Space:O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        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;
    }
}

Here is a simple structure to explain Floyd’s Cycle-Finding Algorithm (Tortoise and Hare) step-by-step:

1. High-Level Concept

Analogy: Explain it like two runners on a circular track. A faster runner will eventually lap and catch up to a slower runner.
Pointers: We initialize two pointers, slow and fast, both starting at the head. slow moves 1 step at a time (slow = slow.next), while fast moves 2 steps at a time (fast = fast.next.next).

2. Why It Works (Mathematical Intuition)

Without a cycle: fast will hit null (the end of the list), meaning no cycle exists, so we return false.
With a cycle: Once slow enters the loop, both pointers are trapped inside it. Because fast gains 1 step on slow in every iteration, the distance between them decreases by 1 node each step until slow == fast, proving a cycle exists.

3. Edge Cases Addressed

Empty List or Single Node: The condition while (fast != null && fast.next != null) cleanly handles head == null or head.next == null without throwing a NullPointerException.

4. Complexity Analysis

Time Complexity: $O (N)$ — If there is no cycle, fast reaches the end in $N /2$ steps. If there is a cycle, fast catches slow within one full loop traversal.
Space Complexity: $O (1)$ — We only use two pointer variables, requiring constant memory.

Obsidian Notes

Explorer