CODEWITHSUNDEEP
linked-list
arun_suresh
arun_suresh

Reputation: 2925

Reversing a linkedList with Nodes having a random pointer

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.

Upvotes: 7

Views: 2177

Answers (4)

Eternalcode
Eternalcode

Reputation: 2412

The below is my attempt at the O(1) solution space solution with O(n) time complexity. 

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;
}

Upvotes: 0

Konstantin Tarashchanskiy
Konstantin Tarashchanskiy

Reputation: 2800

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).

Upvotes: 3

P.A.Kaya
P.A.Kaya

Reputation: 31

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.

Upvotes: 3

Wonerol
Wonerol

Reputation: 101

(Expanding on Konstantin N.'s answer)

To make sure you're not re-reversing anything, you could step through the list, one node at a time, from left to right, and store the index of the last examined node.

lastIndex <- 0
cur <- head

while cur.next not null:
    if cur.random is null:
        randomHead <- # use Konstantin N's findParent helper
        if get_index(randomHead) < lastIndex:
            # we've already examined it
        else:
            # Konstantin N's 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

Upvotes: 2

Related Questions