Reverse linked list with nodes with a random pointer

Question

I recently met this interesting question:

"Consider a linked list with each Node, in addition to the fact that the" next "pointer also has a" random "pointer." A random "pointer points to some random other Node in the linked list. It can also point to NULL. To simplify things, no two" random "pointers point to the same Node, but more than 1 Node a random pointer can point to NULL.

Now we must reverse the direction of all the pointers (both "next" and "random") in the linked list. The limitation is the solution MUST be O (1) the complexity of the space (a constant number of new nodes can be created, but not proportional to the length of the list) "

I spent a lot of time thinking about this. I really am not convinced that this is really possible.

Answer 1

It is very possible. I came up with a solution that is probably not optimal, but shows that this can be done. First, break it into two tasks: flip the following pointers and change the random pointers.

Change the following pointers:

node* last = NULL; node* current = head; node* next = head->next; while (current != NULL) { current->next = last; last = current; current = next; if (current != NULL) next = current->next; } head = last 

Reversing a random list is a bit more complicated because we don’t have a list of all the chapters in the chain of random pointers, but we can find their ends (nodes will have a NULL random pointer). To do this, we need several auxiliary functions. The first is a random list. We basically copy the code from above. Note that we assign the end of the chain to a special value. This stops us from re-reversing the list. See Discussion in the comments for an explanation.

 node* chainTail = malloc(1); //mallocing here to get a unique pointer void reverseRandom(node* rhead) { node* last = chainTail; node* current = rhead; node* next = rhead->random; while (current != NULL) { current->random = last; last = current; current = next; if (current != NULL) next = current->random; } } 

We also need a helper function to find the parent element of the node (or return NULL if it is not). We will do a mute linear search:

 node* findParent(node* target) { node* candidate = head; while ((candidate != NULL) && (candidate->random != target)) candidate = candidate->next; return candidate; } 

Now we just go through the list, find any nodes that have a random NULL value (our chain tails), find their chain heads and reverse the chains:

 node* current = head; //Current node in a linear walk looking for chain tails while (current != NULL) { if (NULL == current->random) { //current is the tail of a random chain, lets find the head node* curr = current; //Current node in the search for the chain hean node* parent = findParent(curr); while (parent != NULL) { curr = parent; parent = findParent(curr); } //At this point, curr is the head of the random chain, so reverse it reverseRandom(curr); } current = current->next; } //Clean up chainTail pointers node* current; for (current = head; current != NULL; current = current->next) { if (current->random == chainTail) { current->random = NULL; } } free(chainTail); //Stop a memory leak if this is not a global 

Standard disclaimer: I do not run this code. He may have errors. I started to sleep near the end, so I may have made a logical mistake, but it seems to me that I'm working.

Also, if you want to put it into production, don't do it. This code works somewhere around O (n ^ 3). This is most likely not the fastest solution. It uses constant space (although even this can probably be reduced by lining and aggressive exchange of variables).

Answer 2

You will also need to consider the case where a random chain forms a (simple) loop. You can detect a loop with a linear circuit traversal; the repeated call will need to be processed again if there is an even number of nodes in the loop.

Answer 3

(Extension of the answer of Konstantin N.)

To make sure you don’t flip anything, you can go through the list, one node at a time, from left to right, and save the index of the last considered node.

 lastIndex <- 0 cur <- head while cur.next not null: if cur.random is null: randomHead <- # use Konstantin N findParent helper if get_index(randomHead) < lastIndex: # we've already examined it else: # Konstantin N reverseRandom() cur <- cur.next lastIndex <- lastIndex + 1 // helper to find node index get_index(node): cur <- head ret <- 0 while cur.next not null: if cur == node: ret <- ret + 1 return ret 

Answer 4

Below is my attempt to solve the space O (1) with the spatial complexity O (n).

 static Node<E> reverseList(Node<E> head) { if(head == null || head.next == null) { return head; } Node<Integer> current = head; Node temp = null; // Reverse an existing Linked list. while(current != null) { Node previousNext = current.next; current.next = temp; temp = current; current = previousNext; } reversedHead = temp; while(temp != null) { if(temp.jump != null) { Node jumpTemp = temp.jump; jumpTemp.jump = temp; temp.jump = null; } temp = temp.next; } return reversedHead; }