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.