repairing a linked list (or: a return to the Circular Lavatory problem)
repairing a linked list (or: a return to the Circular Lavatory problem)
(OP)
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).
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).
Talk To Other Members
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
Spoiler:
Bye, Olaf.
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
Spoiler:
Bye, Olaf.
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
A Maintenance contract is essential, not a Luxury.
Do things on the cheap & it will cost you dear
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
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.
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
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.
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
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).
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
Be careful around the perforations otherwise you'll be writing on your fingers
Chris.
Indifference will be the downfall of mankind, but who cares?
Time flies like an arrow, however, fruit flies like a banana.
Webmaster Forum
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
Yes, I already pointed to the Floyd's Cycle-Finding Algorithm, that also works with two
assisstantsiterators.For example see here: http://ostermiller.org/find_loop_singly_linked_lis...
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.
RE: repairing a linked list (or: a return to the Circular Lavatory problem)
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.