Problem 7.5 - Test for overlapping lists - lists may have cycles

#1

Hi again. I believe I have a slightly easier solution to the problem 7.5 - Testing for overlapping lists - lists may have cycles.

My solution is a small modification to the case when both the lists have cycles. In the solution provided in the book, we first check whether the two lists overlap (and thus have a common cycle) by traversing the cycle starting from the root node (called root2 in the solution) of one of the lists and checking if we hit the root node (called root1 in the solution) of the other list’s cycle. If we don’t, then the two lists do not overlap and we return None.

Now, if we do hit the root node of the other list’s cycle (root1), instead of proceeding to compute the lengths of the two stems, why don’t we just return root1 (or even root2 for that matter)? The problem allows us to return any of the two root nodes and thus root1 is a valid solution in this case. It works even when the two root nodes are in fact the same node.

Here’s the code that I have tested on EPIJudge.

def overlapping_lists(L1, L2):
    root1, root2 = has_cycle(L1), has_cycle(L2)

    if not root1 and not root2:
        # both don't have cycle
        return overlapping_no_cycle_lists(L1, L2)

    if (not root1 and root2) or (not root2 and root1):
        # only one has cycle
        return None

    # both have cycles
    tmp = root2
    while True:
        tmp = tmp.next
        if tmp is root1 or tmp is root2:
            break

    if tmp is root1:
        return root1
    else:
        return None

Output of EPIJudge -
➜ epi_judge_python git:(master) ✗ python3 do_lists_overlap.py
Test PASSED (120/120) [ 34 us]
Average running time: 50 us
Median running time: 49 us
*** You’ve passed ALL tests. Congratulations! ***

The proposed solution runs in almost same time so there’s no performance gain. However, I believe not having to compute the stem lengths is a big plus. :slight_smile:

0 Likes
#2

Hi @amogh09,

The idea is identical to the variant of 7.3 :slight_smile:

The interesting part of this problem is to explain why this work, basically you have to prove the correctness of the case when both have cycles.

It is not trivial to prove that and we just decide to use an easier to explain method, which is reuse the code of 7.4 of this problem.

0 Likes
#3

Hi @tsunghsienlee,

Thank you for your response.

The problem states that,

if one node ends in a cycle, the first cycle node encountered when traversing it may be different from the first cycle node encountered when traversing the second list, even though the cycle is the same. In such, cases you may return either of the two nodes.

We already know that root1 and root2 are respectively the two first nodes encountered when traversing the two lists, right? This is because we get those two nodes using the has_cycle procedure which returns the first cycle node when traversing a list. Doesn’t this complete the proof of correctness of the algorithm for overlapping cycles case?

As for the proof of variant 7.3, I understand that it is non-trivial. One way to do it is to show that the distance k of the first cycle node encountered from the head when traversing the list is congruent to the distance (c - ((s - k) mod c)) modulo c, where c is the length of the cycle and s is number of steps taken by the slower iterator before meeting the faster iterator. (s - k) mod c is the distance of the node where the two iterators meet from the first cycle node, and c - ((s - k) mod c) is the the distance of the first cycle node from the node where the two iterators meet.

This can be shown by using the fact that s = 0 (mod c), because the faster iterator traveled s steps from the meeting point and ended up at the same point.

Could you give me a little more hint as to why the above proof is relevant to the proof of correctness of the case I mentioned?

Sorry for such a long reply.

Thank you!
Amogh

1 Like
#4

Hi @amogh09,

I took a look of your argument again, and it became more clear to me right now that your algorithm is different from variant 7.3 because you use the fact that root1 and root2 respectively the first node in their cycles. Therefore, it is trivial that we shall just use this fact. On the other hand, I think I over-complicate this problem probably.

Again, really appreciate this idea!

1 Like
#5

Hi @tsunghsienlee
I think the original solution was correct. The new solution doesn’t correctly handle the case where the lists overlap before the cycle. It will return the cycle root instead of the first overlapping node

For the case where root1 and root2 are different nodes we can return either of them before calculating stem lengths

0 Likes