repairing a linked list (or: a return to the Circular Lavatory problem)

[lionelhill]

A while ago, I posted a puzzle based on an algorithm for finding out whether a linked list has become circular (obviously just walking round the list is no good, because the algorithm has to have a definite end-point if the list IS circular! Computer-crashes versus computer-doesn't isn't an adequate response).
Circular lavatory problem

So here is a continuation. We assume that you have discovered that your linked list has become circular. Its final node has joined on to some node somewhere in the rest of the list, so it's lasso shaped (a linear bit joins on to a circle). This isn't what you wanted, and now you wish to repair your singly-linked list (either by cutting off the end, or by moving the end to point to the very first node, to make a genuine circular list, or some such strategy)

The problem is this: how do you find the node at the intersection? This is the place pointed to by two different nodes.

Again the task is to find this node without messing up the list (the method must be non-invasive and applicable to any singly-linked list, meaning that it can't mark nodes, because that would involve fiddling with the data-structure of the items in the list). It must not require increasing memory for increasing list-sizes (so no reduplicating the list, or storing pointers to every single node or anything like that!). And obviously it should be as efficient as possible...

(If you prefer to think in the concrete, think of the lavatories again. Your two trusty assistants have met at a lavatory, and therefore know that a ring of closed lavatories exists. How can they find the closed lavatory to which people are being sent from two other closed lavatories? Once again, they are trusty but pretty useless, unable to recognise which buildings they've visited, not allowed to vanadalise council property, and not even equipped with a rudimentary pencil and clipboard. Times are hard in the public sector. They can still follow instructions, they know where they first set off, and they can hear that town clock).

 

[Olaf Doschke]

About the old problem, the solution can also be found for as the "Floyd's Cycle-Finding Algorithm" or "The Tortoise and the Hare Algorithm" of two iterators (assistants) iterating the nodes with single and double speed. When one assistant laps the other, but that doesn't necessarily happens at the intersection node.

Spoiler

Assume two assistants start at node 1 and one iterates with half speed by moving on each second clock strike, the faster assistant will visit double as much nodes by moving each clock strike. When they meet at node 7 of 10 nodes at clock strike 15, the slower has visited 7 nodes and would go to node 8 at the next clock strike, the faster has moved 15 nodes, of which 5 must have been double visited, which are nodes 7,6,5,4 and 3, so 3 is the intersection node. So in general meeting node +1 - double visited nodes

Bye, Olaf.

 

[Olaf Doschke]

That wasn't the final solution.

Spoiler

Thinking about an extreme case: 10 nodes, node 10 points back to node 9, so the loop is nodes 9 and 10 only. The slow assistant arrives at node 9 after 16 clock strikes, the fast assistant then has revisited nodes 9 and 10 several times already and is at node 9 after 16 steps, too. He visited the 9th node 5 times and the 10th node 4 times (because he moved 1-2-3-4-5-6-7-8-9-10-9-10-9-10-9-10-9 in comparison the the slow assistant/iterator 1-1-2-2-3-3-4-4-5-5-6-6-7-7-8-8-9). Obviously 9+1-6 = 4 isn't the right answer, though. I think we need to continue until the next lap and then see how much more steps the faster assistant needs to get 1.5x the loop length. Next steps are 10-9-10 for the fast and 9-10-10 for the slow assistant. So the meet at node 9 after 16 steps and at node 10 after 19 steps. Loop length therefore should be 2 and so node 9 is the intersection.

Bye, Olaf.

 

[IPGuru]

Dosen't keeping a count violate one of the conditions - no storage/ assistants as thick as 2 short ones)?

A Maintenance contract is essential, not a Luxury.
Do things on the cheap & it will cost you dear

 

[lionelhill]

I'll let you count how far your pointers have moved, but I don't think it will help you. Sending one pointer/assistant off at half the speed of the other is indeed a good way to find out whether the list has become a circle, but it doesn't (on its own), I think, give you enough information to trace the branch point.

Put it this way: say you have a chain of 32 nodes that then joins to a ring of 55 nodes. The two pointers/assistants will meet somewhere - I think it will be after the slow pointer has traveled 55 nodes, but it doesn't really matter for this argument. By definition, the fast pointer will have gone twice the distance of the slow pointer (it moves twice as fast), so it doesn't contain any extra information. Note, however, that the two pointers don't always meet exactly at the node where the linear part meets the circle, the target node that we'd like to find. In this example, I think they meet 55-32 = 23 nodes round the circle from the branch-point.

I can get exactly the same result, 55-nodes before the pointers meet, by having a linear list 55 nodes long with the final node pointing to itself. In this case the fast pointer moves to the end and "waits" until the slow pointer catches up, and the slow pointer must catch up at 55 nodes of total travel, and they must meet at the node where the linear part joins the circle, because that is the only node available in the "circle".

Therefore the result, meeting at 55, won't tell us where the join is, because we can get the result "55" from alternative layouts, in some of which we meet at the join, and in others of which we don't.

 

[Olaf Doschke]

Lionel,

good observation, I already found that out and made another approach in my second post. Continuing to the second time they meet you find out the loop length and can then trace that back to the intersection node.
But obviously you thought of another solution not even needing a counter of clock strikes or moves.

Bye, Olaf.

 

[lionelhill]

I need to go and work through your solution on a bit of paper! Thanks for the ideas!

I also realised, thinking about it, that my people-lavatories analogy begins to break down, because my solution (yet to be posted!) finds the node actually at the junction, whereas to repair the list we need to find the node before this. In algorithm world it's very easy, because when stepping along a list we can always keep a pointer one step behind where we are looking, but in the real world of people looking at lavatories, we'd have to assume our assistants can either trace their way back to the previous toilet, or have a massive klaxon horn they can detonate when they find the junction-node, so that another assistant back at the previous toilet knows he's at the right place.

Incidentally, there was never any requirement for only two assistants, although finding the junction-node doesn't need more. The requirement was really for smallish memory-usage that doesn't grow with increasing list-sizes (i.e. the sort of requirement we might make of a genuinely useful algorithm).

 

[ChrisHirst]

I need to go and work through your solution on a bit of paper!

Be careful around the perforations otherwise you'll be writing on your fingers [flush]



Chris.

Indifference will be the downfall of mankind, but who cares?
Time flies like an arrow, however, fruit flies like a banana.
Webmaster Forum

 

[Olaf Doschke]

>Incidentally, there was never any requirement for only two assistants, although finding the junction-node doesn't need more.

Yes, I already pointed to the Floyd's Cycle-Finding Algorithm, that also works with two assisstants iterators.

For example see here:

http://ostermiller.org/find_loop_singly_linked_list.html

This is not a spoiler, as it doesn't discuss a solution to find the junction or the second node pointing to it.

Bye, Olaf.

 

[lionelhill]

Here is a possible solution, for those who are interested:

Spoiler

When the two pointers meet, it will be somewhere in the circular bit. Take one pointer, and move it back to the very beginning. Now step both pointers forward at the same speed. They will meet at the intersection of the circular bit and the linear part.

The reason this works is as follows:
First imagine the two pointers starting together at the very beginning of the straight bit; at this stage we're following Olaf's algorithm to find whether there is a circle at all, so one pointer is moving at twice the speed of the other. Let them move until the slow pointer reaches the intersection.
Let's call the length of the linear bit L, and the length of the circle C
Since the slow pointer has moved all the way to the intersection, L, the fast pointer has moved 2L, i.e. it's moved L nodes round the circle. It is therefore C-L nodes before the intersection.
Incidentally, it doesn't matter whether the circle is very small compared to the linear bit; we just work in modular arithmetic and accept that the fast pointer has whizzed round the circle several times.
Now let's carry on until the two pointers meet. Since the fast pointer must travel twice the distance of the slow pointer, they must meet C-L nodes after the intersection (the slow pointer will have moved a further C-L, the fast pointer will have moved onwards twice this because it started C-L behind).
Since the meeting-point is C-L nodes into the circle, it is C-(C-L) = L nodes before the intersection.
If we now start a pointer at the beginning of the linear bit, it is also L nodes before the intersection (that's how we defined L).
Therefore if the two pointers move at the same speed, they will meet at the intersection.

I love little algorithms like this.