C++ Challenge

Hellp everyone.

Maybe someone can guide me how I can solve this exercise in an efficient way?

Thanks in advance.


http://www.up2me.co.il/thumbs/35229922.bmp

I know that Floyd's algorithm is an O(N) solution to finding a loop in a linked list. You might wanna read about it on Wiki or something. I learnt a version of it recently while solving an ICPC problem from their live archives.

EDIT: You'll soon be taught about trees and graphs in your course if you haven't been taught that already. This video was very useful to me, alongside the tonne of tutorials I viewed at GeeksforGeeks, freecodecamp.org, medium.com, etc...

YouTube

This is my solution:

Code:

---

int findLoop(struct Node* head)
{
    if (head == nullptr)
    {
        return 0;
    }
    int countIndex = 0;
    map<struct Node*, int> mapping;
   
    struct Node* curr = head;
    mapping[curr] = countIndex++;
   
    struct Node* beforeLast = curr;
    struct Node* goThrough = curr->next;
   
    while (goThrough != nullptr && mapping.count(goThrough) == 0)
    {
        mapping[goThrough] = countIndex++;
        beforeLast = goThrough;
        goThrough = goThrough->next;
    }
   
    if (goThrough != nullptr)
    {
        return mapping[beforeLast] - mapping[goThrough] + 1;
    }
     
    return 0;
}

---

Quote:

---

Originally Posted by HelpMeC

This is my solution:

Code:

---

int findLoop(struct Node* head)
{
    if (head == nullptr)
    {
        return 0;
    }
    int countIndex = 0;
    map<struct Node*, int> mapping;
   
    struct Node* curr = head;
    mapping[curr] = countIndex++;
   
    struct Node* beforeLast = curr;
    struct Node* goThrough = curr->next;
   
    while (goThrough != nullptr && mapping.count(goThrough) == 0)
    {
        mapping[goThrough] = countIndex++;
        beforeLast = goThrough;
        goThrough = goThrough->next;
    }
   
    if (goThrough != nullptr)
    {
        return mapping[beforeLast] - mapping[goThrough] + 1;
    }
     
    return 0;
}

---

---

Yikes! That has O(N) space requirement. In other words, the memory it requires is directly proportional to the length of the list. For example, if your list is 1000000 nodes long and has a loop at the 1000000th node, this function will need to fill up the map with 1000000 numbers. It's even worse for BIG lists.

Take a look at Floyd's cycle-finding algorithm (or others on that page) which uses a constant (and small) amount of memory.

Btw, the struct keyword is superfluous in type declarations. Any struct Node* in your function can just be Node*.