$4)$ This exercise is a slightly upscaled version of a challenging interview question.

It is not easy. You do not need to solve it to get an A in this course.

Problems like it will not appear on an exam.

It is solved via careful physical modeling, and is intended to give you practice in careful modeling and careful counting. These are good skills to have, and will be developed in this course. So there is no tragety in not solving the puzzle in week $1.$ Even $4\mathrm{.}1($which is sometimes asked in interviews$)$ requires hints if you are to have any chance of solving it$.$

Let L be a singly linked list where the last record r in the list might not end with r$.$next set to Nil $($or null$),$ but might instead end with r$.$next pointing at $($storing the address of$)$ some other record in L$.$ So thelist ends in a cycle.

You can access these records in the usual way by traversing the list. However, the records are $$read only:$$ you cannot mark them. The storage for your program is limited$.$ In addition to the program instructions, you can only use up to three pointer variables $($i$.$e$.,$ identifiers$)$ and no more than three integer counter variables $($i$.$e$.,$ identifiers$).$ These counts are more than enough to solve the problems below.

For parts $4\mathrm{.}1,4\mathrm{.}2,$ and $4\mathrm{.}3$ below, the solutions should have an operation count that is no more than a$+$b$|$L$|,$ where a and b are constants that should not be too big, and $|$L$|$ is the number of records in L$.$

$4\mathrm{.}1)$ Present a program that can traverse the read only list L$,$ can write information in up to three pointer

variables, and no more than three integer counter variables and which determines if L does indeed end in

a cycle, or if it instead terminates with a pointer to Nil $($or null$).$

Crucial Hint that must be provided: Use two pointers to run down L$.$ One should advance down L in steps of

one record for each iteration, and the other should advance down L in steps of two records per

iteration.

$4\mathrm{.}2)$ Now present a program of the same type $($as in part $4\mathrm{.}1)$ that determines the number of records in the cycle

when L has this peculiar structure. Remember: the records are $$read only:$$ you cannot mark them.

It might also help to think of L as a physical object $$ not a sequence of $3$ records followed by a cycle of $5$

records, but rather a chain of r links that attach to a round wheel with a circumference of s links. The latter

is a concrete abstract model that captures everything in the problem. An example with r set to $3$ and s set to

$5$ is confusing because it is hard to separate what might be some accidental consequence of $3$ and $5,$ and what

is general.

$4\mathrm{.}3)$ Now present a program with the same restrictions as in $4\mathrm{.}1$ and $4\mathrm{.}2,$ which determines the number of records

in the cycle when L has this peculiar structure, and that also computes the number of records in L that

precede the cycle. Remember: the records are $$read only:$$ you cannot mark them.

Comments: Two counts are needed: the number of records in the cycle. and the number of records in the

$$leader$$ that precedes the cycle.

There are several ways to count the number of records in the cycle once both pointers are known to have found

the cycle, but what about the portion of L that does not belong to the cycle? How can you determine its length?

Hint: Sometimes you get $$stuck$$ on a problem because you want to solve it all at once. Instead, you might need to think about processing the data more than once. The idea is to learn something in the first pass over the data that you can use in the second. Moral: not all linear$-$time computations can succeed with just one pass over the data. And even if your code solves part a of a problem perfectly, part b might need a complete rewriting that uses what part a discovered.