LeetCode Tutorial

🚀 Linked List Cycle — LeetCode Problem Solving Tutorial (GoNimbus)

1. Problem Statement

You are given a linked list. Determine whether the linked list has a cycle.

A cycle exists if, at some node, the next pointer points back to a previous node, causing the list to loop infinitely.

Return:

true if a cycle exists
false otherwise

This is one of the most common interview questions because it tests pointer logic, memory intuition, and algorithmic thinking.

2. Why This Problem Is Important

Companies love this problem because it evaluates:

✔ Understanding of Linked List architecture

✔ Ability to reason about pointers in memory

✔ Choosing the right algorithm (tortoise & hare)

✔ Identifying infinite loops

✔ Handling tricky edge cases

Linked List Cycle Visualizer (Floyd’s Algorithm)

Enter Linked List (comma separated): Cycle Position (index):

Status:

🔢 How the Input Works

a) Linked List Values

You enter a list of node values like:

3, 2, 0, -4

Each value becomes a node in the linked list.

Indexes are automatically assigned:

Index:   0   1   2    3
Value:   3   2   0   -4

b) Cycle Position (Index)

This determines where the last node connects back, forming a cycle.

If you enter Cycle Position = 2
→ The last node (index 3) will point back to the node at index 2.

Visual representation:

3 → 2 → 0 → -4
        ↑     |
        |_____|

❌ Cycle Position = -1

This means no cycle is created:

3 → 2 → 0 → -4 → null

🔄 How the Visualizer Builds the Linked List

When you click Create Linked List:

Nodes are created in sequence
Each node points to the next
If cycle index ≥ 0:
- The last node’s next pointer is redirected to the index you selected
The linked list is displayed as visual blocks
The slow pointer (yellow) and fast pointer (red) are placed on the first node

🐢🐇 Floyd’s Tortoise & Hare Algorithm (Step-by-Step)

This algorithm uses two pointers:

Slow pointer (tortoise) → moves 1 step
Fast pointer (hare) → moves 2 steps

This allows the algorithm to detect a loop by checking if both pointers ever point to the same node.

✔ How a cycle is detected:

If the list has a cycle,
the fast pointer eventually laps the slow pointer inside the loop.
When they meet at the same node:

slow === fast  → Cycle Detected

✔ How no cycle is detected:

If fast pointer reaches null
(end of the list), then:

No cycle in the list.

🟡🔴 How the Visualizer Shows Pointer Movement

When you click Next Step:

Slow moves to slow.next
Fast moves to fast.next.next
Nodes update with color indicators:
- 🟡 Yellow = slow pointer
- 🔴 Red = fast pointer

This allows you to visually understand how both pointers move through the list.

🚨 Why Cycle Detection May Happen Immediately

Note:

Both pointers start at the first node
The algorithm checks equality each step

So in some cases—especially with small lists or cycles starting at index 0—slow and fast will match quickly.

This matches how Floyd’s algorithm works:
The meeting point is the signal of a cycle.

3. Intuition — How Do We Detect a Cycle?

A linked list normally ends with:

node -> node -> node -> NULL

But a cycle looks like this:

node -> node -> node
          ↑       |
          |_______|

If we walk through the list with a pointer, we will loop forever.

So how do we detect this without extra memory?

4. Floyd’s Cycle Detection Algorithm (Tortoise & Hare)

This is the famous O(1) space solution.

Idea

Use two pointers:

slow → moves 1 step at a time
fast → moves 2 steps at a time

Reasoning

If there is no cycle,
fast will eventually hit NULL.

If a cycle exists,
fast will eventually “lap” slow, and they will meet.

Visualization in steps:

Step 0: slow = 1, fast = 1

1 → 2 → 3 → 4 → 5  
        ↑         ↓
        ←─────────

Example cycle list (3 → points to 2):

1 → 2 → 3
      ↑   ↓
      ←----

Step	slow	fast	Notes
1	2	3	fast jumps twice
2	3	2	fast wraps in cycle
3	2	2	Met → cycle exists

This guarantees cycle detection in O(n) time and constant space.

5. Algorithm

Create two pointers: slow = head, fast = head
Loop while fast and fast.next are not NULL:
- slow = slow.next
- fast = fast.next.next
If slow == fast → cycle exists
If loop ends → no cycle

6. Time & Space Complexity

Operation	Complexity
Time	O(n)
Space	O(1)

This is optimal — cannot be improved.

7. Go Code (Optimized)

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow, fast := head, head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

8. Python Code

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

9. Edge Cases

✔ 1. Empty list

head = NULL  
→ return false

✔ 2. Only one node

node1 → NULL
→ return false

✔ 3. One node forming a cycle

node1 → points to itself
→ return true

✔ 4. Large list with cycle at the end

✔ 5. Cycle in the middle

How It Works

User enters node relationships
Visualizer simulates slow/fast pointers
Shows whether a cycle exists

      slow
       ↓
1 → 2 → 3 → 4
      ↑     ↓
      ←─────
         ↑
        fast

Linked List Cycle Cheat Sheet

Use Floyd’s Tortoise & Hare algorithm
Two pointers: slow + fast
If they meet → cycle exists
If fast reaches NULL → no cycle
Time: O(n), Space: O(1)

Absolutely — here are 50 interview-style questions and answers specifically focused on the Linked List Cycle (LeetCode 141 + related concepts).
These cover core logic, edge cases, mathematical intuition, pointer behavior, complexity, variations, and common mistakes — perfect for GoNimbus learners.

✅ 50 Interview Questions & Answers — Linked List Cycle

🔹 Basics & Core Logic

1. What is a cycle in a linked list?

A cycle exists when a node’s next pointer points to a previous node, causing infinite traversal.

2. How do we detect a cycle in a linked list?

Using Floyd’s Tortoise & Hare algorithm: move slow 1 step, fast 2 steps. If they meet → cycle.

3. Why do slow and fast pointers meet if a cycle exists?

Because the fast pointer moves faster; inside a loop, it eventually catches up to the slow pointer.

4. Can a cycle start at index 0?

Yes — if the tail connects back to the head.

5. What does `pos = -1` represent?

-1 means no cycle (the tail points to null).

🔹 Algorithm Behavior

6. When do we return false?

If fast == null or fast.next == null during traversal.

7. Why check `fast.next != null`?

Because the fast pointer needs to move two steps; if the second step is null, list ends → no cycle.

8. What happens if the list is empty?

No nodes → no cycle → return false.

9. What if the list has only one node?

If its next points to itself → cycle
If next = null → no cycle

10. Why do slow and fast pointers both start at the head?

To ensure they traverse from the same starting reference.

🔹 Mathematical & Logical Intuition

11. Why does Floyd’s algorithm guarantee detection?

Because relative speed ensures fast will overlap slow in a finite number of steps inside a cycle.

12. Does the meeting point indicate the start of the cycle?

No — it only confirms a cycle exists.
(LeetCode 142 uses the meeting point to find the cycle start.)

13. What is the worst-case number of steps before they meet?

O(n) steps — they will meet within one full cycle loop.

14. What if the slow pointer enters the cycle late?

Fast will lap slow inside the cycle; meeting is still guaranteed.

15. Does cycle size affect detection?

Yes — larger cycles take more steps until the pointers meet.

🔹 Edge Cases

16. Can two different lists share the same cycle?

Only if they physically share node references.

17. Can the cycle connect to any node?

Yes — any valid index is allowed except -1.

18. What if all nodes in the list form a cycle?

Detection still works — slow and fast meet inside the loop.

19. Can a cycle occur in the middle of the list?

Yes — the start of the cycle can be anywhere.

20. What happens if the cycle is only one node long?

A self-loop is still a valid cycle.

🔹 Complexity & Optimization

21. Time complexity of Floyd’s algorithm?

O(n)

22. Space complexity?

O(1) — only two pointers.

23. Can we detect cycles using a hash set?

Yes, by storing visited nodes.
But that uses O(n) space.

24. Which method is optimal for interviews?

Floyd’s Tortoise & Hare algorithm.

25. Why is two-pointer method better than hashing?

Because it achieves constant memory usage.

🔹 Memory & Reference Concepts

26. What does it mean if slow == fast?

Both pointers refer to the same node → cycle detected.

27. Why do we compare node references, not node values?

Different nodes may have equal values, but cycles depend on memory addresses.

28. Can duplicated values cause incorrect detection?

No — pointers compare references, not values.

29. Why not check visited values instead of nodes?

Same values can appear multiple times; values do NOT indicate cycles.

30. Does the direction of traversal matter?

Linked lists are one-directional — cycles occur through next pointers only.

🔹 Variations Asked in Interviews

31. How to find the length of the cycle?

After slow and fast meet, move one pointer until it returns to the meeting point; count steps.

32. How to find the starting node of the cycle?

After meeting, reset slow to head; move both one step at a time; first meeting point is cycle start.

33. How to break the cycle once found?

Find the cycle start and then find the previous node in cycle; set its next to null.

34. How to detect if two lists intersect inside a cycle?

Detect cycle in each, then compare cycle nodes.

35. Can two-pointer method detect multiple cycles?

No — a linked list can have only one cycle.

🔹 Common Mistakes

36. Forgetting to check fast.next for null.

This causes a runtime error.

37. Comparing node values instead of references.

Incorrect — must compare pointer equality.

38. Using `slow = head.next` initially.

Incorrect starting point; both must start at head.

39. Moving slow two steps and fast one.

Opposite speeds break the algorithm.

40. Forgetting edge cases: empty list or one node.

Always check these first.

🔹 Deep Understanding Questions

41. Why is the fast pointer twice as fast?

To ensure relative movement; a speed difference of 1 guarantees meeting.

42. Could fast move 3 steps and slow 1?

Yes, but unnecessary — 2 steps is optimal and reduces pointer jumps.

43. Is this algorithm deterministic?

Yes — it will always detect a cycle if present.

44. Why does meeting inside the cycle guarantee a loop?

Because two pointers moving at different speeds only collide in a closed path.

45. Can Floyd’s algorithm detect the exact cycle length alone?

Yes — by looping one pointer after meeting.

🔹 LeetCode-Specific Questions

46. Why does LeetCode use `pos` in input but not in the function?

pos is only for constructing test cases; actual cycle detection must not rely on it.

47. Why does LeetCode say `pos = -1` means no cycle?

It indicates tail.next = null during input creation.

48. Can LeetCode input contain negative node values?

Yes — values do not affect cycle detection.

49. Do node values influence the cycle logic?

No — cycle detection depends purely on pointer links.

50. Can the algorithm run forever in a cyclic list?

No — pointers meet in O(n) time and algorithm terminates.