• @hobovsky

    Thanks for the suggestion. Its actually what I did and it helped me solve the problem. I read about the problem and the theory behind the solution, after looking at some different algorithms for that I wrote down one I particularly liked and after understanding how and why it worked I used it to solve the problem and was actually quite amazed at how inefficient I had been approaching the problem. My solution used to run at about 108. something ms on the basic tests, and the solution I submitted ran the same tests with a new one I made with 1 million cycles faster than that.
    Again, thanks for the suggestion and for future readers I really recommend reading up on this as it does make a lot of sense when it finally clicks

  • it seems you have more than one problem with your approach:

    • you use additional list to store visited nodes. While this is not that bad, this problem can be solved with O(1) additional memory, i.e. you do not need to store every visited node anywhere. You are right that you need to loop through all the nodes, but it does not mean that you need to remember every of them.
    • whats worse, you use a linear list as your container, and perform linear lookup on it. this is bad, and its the cause of your timeouts here. if you are going to use additional storage (which you don't have to), use something with more efficient lookup.
    • nodes indeed do not have any associated value, but its not necessary. reference equality is all whats needed.

    I suggest doing some more research (i.e. googling) and looking for some loop detection algorithms. you will definitely find something.

  • C#

    Im stopping for now as obviously Im missing something. My tests pass but I get a time out at the actual attempt. I'm using a single linear loop to go through all of the nodes, adding them to a List and checking if the current node I am at is present in the list. If present, It means I have looped through all of them, so then I just return the count - the index of the current node.
    I guess it should have a simpler solution judging by some of the comments in the Discussion but Im stuck for now, will come back to it later. I dont really see how you can figure this out without looping through all the nodes, because you only have node.next, and nothing else to indicate what text or something this node has (Judging by the image, they should have some text in them), I tried using the node itself, text, Text, GetText, value, Value, but none seem to give me any values. I also tried using reflection to print out the properties and also got only .next.

  • This comment is hidden because it contains spoiler information about the solution

  • Using Ruby.

    #use this if you want to create your code on you computer the class of the node is in the description

    The the Node class is not in the description.

    When running "Test", I get an unexpected error:

    Response received but no data was written to STDOUT or STDERR.

    Even when I tried with a very simple solution that's wrong but should not "break":

    def loop_size(node)
      puts "Hello"
  • Rust translation ready for review. Fyi, I used the arena pattern because not leaking memory in reference cycles is really hard in a non garbage collected language.

  • great explanation, thank you very much! Learned a lot of those tiny sentances.

  • You cannot get the end of the list, because there's no end. Nodes are connected in a loop, and there's no last node.

    The fact that nodes are pointed by reference is helpful though. you can still compare references for equality, so node1 == node2 will be true if both variables point to the same instance of a node. You can use this fact to find the loop.

  • hi, if I dont have the last element in the LinkedList (None) how can I solve this, any hints woyld be great.
    becuse we cant work wih node.value I will always get a prepended object (memeoryreference) wich dont give much.
    node will always show memoryreference and it will consider anything else but None, so how can I get the end of the linkedList? any hints?.
    should I recursive this?

  • You have a node.setNext method that you didn't even mention in the description of this Kata. This is obviously crucial in solving this.

    No, it's not. setNext is an implementation detail and not a part of the interface. getNext( ) is all you need to solve the kata.

  • The description explicitly states:

    Note: do NOT mutate the nodes!

    You do not need node.setNext() nor should you use it. The only part of the interface that you need is mentioned in the description: node.next.


  • There needs to be more of a description here than just briefly mentioning the two methods added as properties on the 'node' object argument. I have to console log just to clarify everything for myself. You have a node.setNext method that you didn't even mention in the description of this Kata. This is obviously crucial in solving this. Please update the description to include a clear picture of what your passing into the function as an argument.

  • You got it though, congratulations!

  • I was storing each of the nodes and then iterating through the node list to find a repeat. I had to google other algorithms to use because iterating through a massive list to find a revisted node was taking too long. I wouldn't say "it's as simple as that." I understand that you need to find the first revisted node... but HOW you quickly find the first revisited node is the crux of the problem that I couldn't discover completely on my own without google algorithm help.

  • Loading more items...