you have an unidirectional list, where each element has pointer pointing to a random element forward in the list. This additional pointer allows to skip positions in the list, but this skip amount is not constant and changes randomically with the position.
Copy the list with constant space.
I have an O(n) solution, but I have made the following four assumptions. If any of them is invalid, please let me know.
ReplyDeleteA1. I am supposed to allocate the copy of the list.
A2. I am allowed to allocate the copy as one contiguous block of memory.
A3. I am allowed to cast integers into pointers and vice-versa.
A4. I am allowed to write to the original list, as long as I restore it to the original state before returning the result.
Furthermore, let's establish some notation. A Node consists of three fields: value, next, random. We are given a pointer to a Node in_start, we are supposed to return a pointer to a Node out_start.
The algorithm proceeds then the following way:
bool null_terminated;
int n = 0;
// Determine length and termination type.
{
Node* in_curr = in_start;
while (in_curr != in_start && in_curr) {
++n;
in_curr = in_curr->next;
}
null_terminated = in_curr == NULL;
}
Node* out_start = new Node[n];
// Copy values, store in.random as out.next,
// overwrite in.random with indices.
{
Node* in_curr = in_start;
for (int i = 0; i < n; ++i) {
out_start[i].value = in_curr->value;
out_start[i].next = in_curr->random;
in_curr->random = static_cast(i);
in_curr = in_curr->next;
}
}
// Populate out.random.
for (int i = 0; i < n; ++i) {
Node* in_curr = out_start[i].next->random;
int index = static_cast(in_curr);
out_start[i].random = &(out_start[index]);
}
// Restore in.random, populate out.next.
{
Node* in_curr = in_start;
for (int i = 0; i < n; ++i) {
in_curr->random = out_start[i].next;
out_start[i].next = &(out_start[i + 1])
}
}
// Terminate out correctly.
if (null_terminated)
out_curr[n - 1].next = NULL;
else
out_curr[n - 1].next = out_curr;
return out_start;
it's ok that you allocate the copy list, and modify the list. So i like your solution
ReplyDelete