4.1 Test for cyclicity; variant solution

#1

i was looking at 4.1 Test for cyclicity problem (find the origin of cycle in a linked list, if any).

it gives one solution, then the variant question goes:

Variant: The following program purports to compute the beginning of the cycle
without determining the length of the cycle; it has the benefit of being more succinct
than the code listed above. Is the program correct?

public static ListNode <Integer > hasCycle(ListNode <Integer > head) {
    ListNode <Integer > fast = head , slow = head;
    while (fast != null && fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) { // There is a cycle.
            // Tries to find the start of the cycle.
            slow = head;
            // Both pointers advance at the same time.
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow; // slow is the start of cycle.
        }	
    }
    return null; // No cycle.
}

this seems to implement Floyd’s cycle-finding algorithm which doesn’t determine the length of cycle either. so i’m inclined to think this code actually works… possibly you’re asking this because it doesn’t handle edge cases correctly as is written (?), but isn’t the core algorithm still correct?

or maybe the answer to variant question really was, ‘yes, this code works too’…

0 Likes
#2

Probably we should slightly modify the question to “Is it correct? Please also explains your reason.” BTW, there is also one important unanswered here—is the return value actually points to the start of cycle?

0 Likes
#3

is the return value actually points to the start of cycle?

yes. notwithstanding any possible bit of mistakes in the code, the explanation on why/how it works would basically be the same as the explanation for how floyd’s cycle algorithm works (some ppl tried here: https://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work)…

purports to compute the beginning of the cycle without determining the length of the cycle

yes, you don’t need to determine the length of the cycle to find its origin.

it’s just that, the way the question was presented/phrased in the book really makes it sound like you were expecting ‘no’ as the answer (first of all, it wasn’t presented as one of the solutions, and if it’s “more succinct” as you’ve said it, why wasn’t it?)… floyd’s cycle algorithm is already hard to understand even when you know it works (as can be seen from quora link above), but instead of presenting the algorithm w/ accompanying explanation, you’re asking general readers if it works at all… the first time i learned of it (a few years back), it took me a while before i got it/ and that’s with me given a mathematical proof similar to one above in the book.

so, i might be wrong on my opinion, but i really don’t expect a lot of readers to get it if they were to be asked if it works at all w/o any explanation/proof from the given book… and they don’t know the name of this algorithm, so they can’t even look up online. they would just come up w/ a random reason on why/how they think it won’t work (which would be wrong) and move on…

0 Likes
#4

I think you are too smart such that you overthinking a little bit :grin:

The answer is “yes” and like you said and provided in the link in Quora. Some simple arithmetic will prove this answer. However, it probably won’t appear in real interview as you said; our goal is to stimulate readers’ thinking by solving interesting problems. You definitely a good example here that think all possible situation to make this algorithm work/don’t work. Now you have a very steady grasp on such type of problem now!

0 Likes
#5

@tsunghsienlee the answer in the book where pointer is C ahead of another is very difficult to understand. Can you please explain.

Once we know there is a cycle, and we have a node on it, it is trivial to compute the cycle length. To find the first node on the cycle, we use two iterators, one of which is C ahead of the other. We advance them in tandem, and when they meet, that node must be the first node on the cycle.

I could prove it when s + x = c, where

  • s is the distance from the head to the start of the cycle,
  • x is offset in the cycle where the fast and slow pointers meet, and
  • c is the length of the cycle.

Proof:

  • When you travel the distance c (= s + x) from the start you have entered the cycle and x nodes from start of the cycle.
  • Now, you need to travel s more nodes to complete the cycle and be at the start. This is because c = s + x.
  • So after s nodes you be the start of the cycle, and that is when you meet the other pointer that started from head which also covered s nodes to reach you.

s + x = n c , where n > 1. IDK?

0 Likes