Is there a non-destructive solution without using extra space?


  • 1
    Y

    Basically, I came up with an accepted solution without using extra space, but destructed the linked list internally. The way I did was that after traversing the current node but before moving to the next node, I make the next pointer pointing to the current node.

    This works fine but resetting the next pointer really annoys me. Other solutions I saw from the discussions either change the next pointers in other ways, or rely on a lucky number for the val of the node.

    I was wondering if anyone has a non-destructive solution, in the way that it preserves all the next pointers, that uses no extra space?

    Thanks!


  • -1
    M

    actually there is. this method is called Floyd’s Cycle-Finding Algorithm. this is also considered the fastest method. what you precisely do is take two pointers, one that is incremented once, and another that is incremented twice. lets name them slow_ptr and fast_ptr. Suppose we have a linked list like 1->2->3->4->2 where the last 2 actually means that 4 is looping back to the 2 at first index. now the slow_ptr will move as follows : 1->2->3->4 and the fast_ptr will move as : 1->3->2->4.
    at this point, they both point to the same node, and hence we can return true. if at any point we find a null, we can simply return false.
    here is my code to make things more clear.
    p.s. : this solution took 52 ms.

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            ListNode *slow_ptr = head, *fast_ptr = head;
            while(slow_ptr != NULL && fast_ptr != NULL && fast_ptr->next != NULL)
            {
              slow_ptr = slow_ptr->next;
              fast_ptr = fast_ptr->next->next;
              if(slow_ptr == fast_ptr)
                return true;
            }
            return false;
        }
    };  

  • 0
    Y

    Thanks1 This algorithm makes great sense, and it does maintained the linked list structures. I do have follow-up questions regarding the algorithm design and performance. First of all, I am not sure if this can be called using no extra space. An naive algorithm that takes O(n^2) time can use a single pointer or temporary variable for a node then loops till the end to see if there is any cycle back to it. While that algorithm has a worse performance, it also says to use some extra space, to record the "current" node. Would it be good enough for us to say this algorithm uses no extra space? Another question is, this algorithm has a linear time complexity, which is great. However, I have hard time understanding why it is considered the "fastest". Maybe you mean the fastest among all non-destructive algorithm? I was asking because if we simply change each node's pointer back to itself before moving to the next, the absolute steps to identify a cycle is less than Floyd's algorithm, though they bears the same linear time complexity. Any comments? Thanks again for your algorithm.


  • 0
    M

    i think you are a little confused regarding what using extra space means. of course we are using two additional pointers here, but pointer in a typical compiler takes just 4 bytes of memory. two of them would become 8. now one node of our linked list takes 8 bytes of memory. suppose our linked list has 1000 nodes. that would make up to 8000 bytes of memory. now 8 compared to 8000 is almost negligible. now suppose we have only 4 nodes. that would take 32 bytes of memory. but still the memory we are using for those pointers is 8. that means that the memory we are using does not depend on the size of our list, which will be the input. it is constant. hence we say that this algorithm uses no extra space or has space complexity O(1). compare this to using a stack or some other structure where the memory we would be using would be proportional to the size of our list.

    technically, i agree with you that some space is being used, but since its constant with respect to the input, it is usually termed as "no extra space".


  • 0
    M

    regarding the rest of your question, i dont really know why it is considered the fastest. but definitely any algorithm that does not preserve the original structure of our input is not considered good enough.

    i would like to add there are other algorithms also, one in particular, brent's algorithm. that claims to be faster than Floyd's in some cases. but i have not really been able to understand the algorithm well.

    also, there is a follow up to floyds algorithm, once we have found that there is a loop, we can also find where the loop begins just as easily. would you like to know?


  • 0
    Y

    I think it's good enough so far. Thanks for all the help! ;-)


Log in to reply
 

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