How to differentiate an infinite linked list versus a linked list with cycle?

  • 0

    Suppose you have two linked lists.  One is infinite meaning when you start at the beginning and go to the next node you will always get a next node.  One is circular meaning the last element points to the first element.  For this list the same condition holds - you will always get a next node. Given one of these lists, how do you determine if it's the circular one or not?

    I consider this problem is slightly different from the original one. Is there a solution to my problem?

  • 1

    if the list is infinite, you can never tell the list has a circle or not.

    The thing is , if all you can do is to check the next node, when the list is infinite, you have no method to judge the list is finite or infinite.

  • 0

    I think you can. You just need to go through the list and mark every element with some flag (in this case - you can set value to null/None), and if you find the makred item - it has lists, if you come to the end of the linked list - it doesn't.

    For some reason such code will also work for this task at least for Python :)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.