DAY 40: Solved Cycle Detection, Cycle Length, Start of Cycle & Happy Number Problems | Linked List

---

🚀 Introduction

Welcome to Day 40 of my DSA Journey!
After spending an intense few weeks focused on Recursion, I’ve now shifted my focus to one of the most fundamental data structures in DSA — the Linked List.

Transitioning from recursion to linked lists has been a rewarding step, as these concepts are closely connected, especially when solving problems involving traversal and pointer manipulation.

Over the past 3 days, I’ve solved several key problems on the Singly Linked List, including: Cycle Detection, Length of Cycle, Find Starting Point of Cycle, and Happy Number.

I’m sharing this journey publicly to maintain consistency and help others who are starting their DSA path from scratch.

Feel free to follow me on Twitter for real-time updates and coding insights!

📅 Here’s What I Covered Over the Last 3 Days:

Day 37

• Cycle Detection
• Length of Cycle

Day 38

• Find Starting Point of Cycle

Day 39

• Happy Number

Let’s dive into each of these topics in detail below 👇

---

Q 1. Cycle Detection in Linked List:

The task is to determine whether a given singly linked list contains a cycle (loop).
A cycle occurs if a node's next pointer points to a previous node in the list, forming a loop.

Example:

Consider the linked list: 1 → 2 → 3 → 4 → 2 (cycle back to node with value 2)

Here, node 4 points back to node 2, forming a cycle. The function should return true.

Approach:

We use the Tortoise and Hare (Fast & Slow Pointers) technique:

• Initialize two pointers, slow and fast, at the head of the list.
• Move slow one step at a time and fast two steps at a time.
• If the list contains a cycle, slow and fast will eventually meet.
• If fast reaches the end of the list (null), there is no cycle.

This approach efficiently detects a cycle in a single pass without extra space.

Why It Works?
Since fast moves twice as fast as slow, if there is a cycle, fast will eventually "lap" slow and they will meet inside the cycle. If no cycle exists, fast will reach the end of the list and the loop terminates.

Code:

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;
}

Time & Space Complexity:

• Time Complexity: O(n)
  Both pointers traverse the list at most once.

• Space Complexity: O(1)
  Only two pointers are used, no extra space needed.

Final Thoughts:

• The Tortoise and Hare technique is optimal for cycle detection.
• It works without modifying the linked list or using extra memory.
• This method can also be extended to find the length of the cycle or the starting node of the cycle.

---

Q 2. Find Length of Cycle in a Linked List:

Given a linked list, determine the length of the cycle if a cycle exists. If there is no cycle, return 0.

Example:

Consider the list:
1 → 2 → 3 → 4 → 5 → 3 (cycle starts again at node with value 3)

The cycle is: 3 → 4 → 5 → 3, so the length of the cycle is 3.

Approach:

We use the Tortoise and Hare (Floyd's cycle detection) technique:

1. Initialize two pointers, slow and fast, at the head of the list.
2. Move slow by one step and fast by two steps.
3. If slow equals fast, a cycle exists.
4. To find the length of the cycle, move fast one step at a time until it meets slow again, counting the number of steps taken.

Code:

private static int lengthOfLoop(Node head) {
    Node slow = head;
    Node fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if(slow == fast){
            return findLength(slow, fast);
        }
    }

    return 0;
}

private static int findLength(Node slow, Node fast) {
    int count = 1;
    fast = fast.next;

    while (slow != fast) {
        count++;
        fast = fast.next;
    }
    return count;
}

Why It Works?

• Once slow and fast meet, they are inside the cycle.
• By moving one pointer around the cycle until it meets the other again, we count the exact number of nodes in the cycle.
• This works because the meeting point is guaranteed to be inside the cycle, and traversing the cycle once gives its length.

Time & Space Complexity:

• Time Complexity: O(n)
  Detecting the cycle takes O(n), and counting nodes in the cycle also takes O(n), so overall O(n).

• Space Complexity: O(1)
  Only two pointers are used; no extra space is required.

Final Thoughts:

• This method efficiently calculates the cycle length without modifying the list.
• It leverages the Tortoise and Hare technique for both detection and length calculation.
• Knowing the cycle length is helpful for further operations, such as finding the starting point of the cycle.

---

Q 3. Find Starting Point of Cycle:

Given a linked list, find the node where the cycle begins. If there is no cycle, return null.

Example:

Consider the list:
1 → 2 → 3 → 4 → 5 → 3 (cycle starts again at 3)

The starting point of the cycle is the node with value 3.

Approach:

• Use two pointers, slow and fast, starting at the head.
• Move slow one step and fast two steps at a time.
• If they meet, a cycle exists.
• To find the starting node:
  • Reset slow to the head.
  • Move both slow and fast one step at a time until they meet again.
  • The meeting point is the starting node of the cycle.

How This Approach Works?

• When slow and fast meet inside the cycle, the distance from head to the start of the cycle equals the distance from the meeting point to the start of the cycle along the cycle path.
• By resetting slow to head and moving both pointers one step at a time, they will meet exactly at the cycle’s starting node.

Code:

public Node findStartingOfLoop(Node head) {
    Node slow = head;
    Node fast = head;

    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if(slow == fast) {
            slow = head;
            while (slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }

    return null;
}

Time & Space Complexity:

• Time Complexity: O(n)
  Detecting the cycle takes O(n), and finding the starting node also takes O(n), so overall O(n).

• Space Complexity: O(1)
  Only two pointers are used; no extra space is required.

Final Thoughts:

• This method efficiently finds the start of the cycle without modifying the list.
• It builds upon the Tortoise and Hare technique used in cycle detection.
• Knowing the starting point is crucial for further linked list operations or cycle removal.

---

Q 4. Happy Number:

A Happy Number is defined as a number that will eventually reach 1 when replaced by the sum of the squares of each digit repeatedly.
If it loops endlessly in a cycle that does not include 1, then the number is not happy.

Example

• Input: n = 19
  Process:
  1² + 9² = 1 + 81 = 82
  8² + 2² = 64 + 4 = 68
  6² + 8² = 36 + 64 = 100
  1² + 0² + 0² = 1
  Output: true (Happy Number)

• Input: n = 2
  Process:
  2² = 4
  4² = 16
  1² + 6² = 37
  3² + 7² = 58
  5² + 8² = 89
  ... (loops in cycle: 89 → 145 → 42 → 20 → 4 → 16 → 37)
  Output: false (Not a Happy Number)

Approach:

We use Floyd's Tortoise and Hare cycle detection algorithm:

1. Treat the process of repeatedly computing the sum of squares as moving through a linked list of numbers.
2. Use two pointers:
   • slow moves one step at a time (computes sum once).
   • fast moves two steps at a time (computes sum twice).
3. If at any point fast == 1, the number is happy.
4. If slow and fast meet at a number other than 1, a cycle exists (not a happy number).

How to Think of Linked List Here?

Even though there’s no explicit linked list, the sequence of numbers generated can be seen as nodes in a linked list.

• Each number points to the next number generated by the sum of squares operation.
• If a number repeats, we’ve found a cycle, just like in a linked list with a loop.

Example with n = 2:
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (cycle detected)

Code:

static boolean isHappy(int n) {
    int fast = n;
    int slow = n;

    do {
        slow = sumOfSquaresOfDigits(slow); // move 1 step
        fast = sumOfSquaresOfDigits(sumOfSquaresOfDigits(fast)); // move 2 steps
        if (fast == 1) {
            return true;
        }
    } while (fast != slow);

    return false;
}

static int sumOfSquaresOfDigits(int n) {
    int sum = 0;

    while (n > 0) {
        int rem = n % 10;
        sum += (rem * rem);
        n = n / 10;
    }

    return sum;
}

Time & Space Complexity:

• Time Complexity: O(log n)
  Each sum-of-squares step reduces the number size significantly. Cycle detection runs in linear time relative to sequence length.

• Space Complexity: O(1)
  Only two integer variables are used.

Final Thoughts:

• This problem is a great example of applying linked list cycle detection in a non-linked list scenario.
• Treating the sequence of numbers as a linked structure allows efficient detection of cycles.
• The approach avoids extra space and works optimally for checking happy numbers.

---

5. What's next:

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

6. Conclusion:

In this blog of my dsa journey, we explored four important problems that not only strengthen our understanding of Linked Lists but also improve our problem-solving skills:

• Cycle Detection – Identifying whether a loop exists using the Tortoise and Hare algorithm.
• Length of Cycle – Calculating the number of nodes in a detected loop.
• Find Starting Point of Cycle – Pinpointing the exact node where the cycle begins.
• Happy Number – Applying cycle detection logic in a non-linked list scenario.

These problems highlight the power and versatility of the Floyd’s Cycle Detection Algorithm, showing how a single core idea can be adapted across multiple contexts.

By mastering these concepts, I'm building a strong foundation for more advanced data structure problems and developing an intuition for applying known patterns to new challenges.

If you're on a similar learning path, feel free to follow along or reach out — let’s grow together.