lionelhill
Technical User
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).