Reversing a linkedList with Nodes having a random pointer

Question

I recently came across this interesting question :

"Consider a Linked List with each Node, in addition to having a 'next' pointer also has a 'random' pointer. The 'random' pointer points to some random other Node on the linked list. It may also point to NULL. To simplify things, no two 'random' pointers will point to the same node, but more than 1 Node's random pointer can point to NULL.

Now we are required to reverse the direction of all the pointers (both the 'next' and 'random') of the Linked list. The constraint is the solution MUST be O(1) space complexity (A constant number of new nodes can be created but not proportional to the length of the list)"

I spent quite a lot of time mulling over this. Im not really convinced it is actually possible.

Answer 1

You would also need to account for the case where the random chain forms a (simple) cycle. You could detect the cycle with a linear traversal of the chain; again re-reversal will have to be handled if there are an even number of nodes in the cycle.

Answer 2

It is very possible. I came up with a solution that is likely not optimal but shows that it can be done. First break it apart into two problems: reversing the next pointers and reversing the random pointers.

Reversing the next 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 the random list is a bit trickier, just because we do not have a list of all of the heads of random pointer chains, but we can find the ends of them (the nodes will a NULL random pointer). We will need several helper functions to do it. The first is one to reverse a random list. We largely copy the code from above. Note that we are setting the end of the chain to be a special value. This stops us from re-reversing a 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 of a node (or return NULL if there is none). We will do a dumb linear search:

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

Now we just walk the list, find any nodes that have a random value of NULL (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 have not run this code. It may have bugs. I started to get sleepy near the end, so I may have made a logical error, but it seems to me to work.

Also, if you are looking to put this into production, don't. This code runs somewhere around O(n^3). This is very likely not the fastest solution. It does use constant space (though even that can probably be reduced by in-lining and aggressive variable sharing).