Can you get the loop? – Codewars C++ Solution

Codewars has been a great platform for computer science students to nourish their coding skills. There are great problems to solve on topics like Data Structures, Algorithms, simple loops, etc. Codewars provide coding exercises in almost every programming language. We are going to solve a problem related to Linked List in Codewars C++  programming language. To know more about the problem, click here.

In this problem, a cycle of the linked lists has been provided along with a tail.

Linked List Cycle With Tail

We have to find the length of the cycle of the Linked list discarding the length of the tail. E.g., the length of the above-shown image would be 3, not 4, because we are discarding the length of tail A which is not contributing to the cycle.

The started Code given by Codewars in C++ is:

int getLoopSize(Node* startNode)
{ 

}

Note: The startNode can point to any Node in the Cycle or the tail Node. 

What would be your approach to this problem? Comment and let everyone know.

My Approach to the Problem

  1. Let’s say the start node is Pointing towards the tail Node First.
  2. If we start a loop from StartNode until it gets back to the same node, we will run into an infinite loop problem. E.g., we started with Node A then getNext() will move the StartNode to N1 after calling two more getNext() functions, it will get to N1 again, which was not the startNode ( The startNode was A), so it will never get back to the Tail Node again, and we will run into an infinite loop problem. 
  3. The best approach is to make a list of nodes from which you have gone through. For Example, we have created a List called X, as StartNode is A, let’s put this into X, so X = [A], after StartNode pointed towards Next Node the X=[A, N1]  Similarly, after the cycle completed X=[A, N1, N2, N3].
  4. Now when to end the Loop? For instance, we have to end the loop when startNode completed its cycle and gets back to the N1 again. Look for N1 in List X. If it is present, end the Loop. 
  5. In conclusion, we have to return the length of the cycle; when StartNode completed its cycle, it gets back to N1. We have to take the position of N1  and count elements after it, including N1. For e.g, X=[A,N1,N2,N3]. The Position of N1  is 1, and the elements after and Including N1  is 3, which is the returned value we want.

Code the solution in C++

  1. Create a vector to store the Nodes.
  2. Int count variable to store the return value.
  3. Check for StartNode in Vector. 
  4. End the Loop if StartNode is present in the Vector
#include <vector>
using namespace std;
int getLoopSize(Node* startNode)
{
  vector<Node*> temp;
  int count = 0; 
  while(1){
    temp.push_back(startNode);
    startNode = startNode->getNext();
    for(auto i = temp.begin(); i != temp.end(); i++){
      if(*i == startNode){
        while(i != temp.end()){
          count++;
          i++;
        }
        return count;
        break;
      }
    }
  }
}

 

READ MORE

C++ related posts Visit HERE

Python-related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Share the Knowledge