CODEWITHSUNDEEP
algorithmdata-structureslinked-list
Yogesh
Yogesh

Reputation: 563

In a linked list, to Reach the last node via auxiliary links

We have a linked list with node structure:-

struct Node {
   Node *next;
   Node *aux;
};

structure of the linked list:-

  1. next pointer always points to the next node, as in a singly linked list.
  2. aux pointer can point to any node, before or after the current node, to current node itself, it can be NULL as well.

Problem statement: Do minimum number of modifications to the aux pointers in the list, so that last node is reachable from any node of linked list via auxiliary pointers. e.g. Once all the modifications are done, restriction to reach the last node is that we can use only aux pointer to navigate the list. Following is one of the possible representation of list. Note that aux pointer being NULL is not represented here. enter image description here

Upvotes: 0

Views: 320

Answers (1)

Sorin
Sorin

Reputation: 11968

First a few observations:

The null aux pointers obviously need fixing, so just point them to the end.

For the others, if you keep following the pointers, they will either reach the last node so you don't need to do anything, or they will loop. If they loop then the elements on the loop will belong to exactly one loop (because you have a single aux pointer). You can pick any element of the loop to fix (since it's a loop all the other will eventually reach the fixed element).

There's no point in making a aux pointer point to anything other than the last element. That's the goal and pointing to anything else could potentially introduce a loop.

So with this mind the algorithm is simple: Start with a vector of int where everything is 0. You'll need an id-generator (just an int to keep incrementing, starting at 1)

  • Iterate through the vector.

  • If the entry is not 0 move to the next entry in the vector.

  • Otherwise get the next id from the generator (and increment it for the next time). Mark the node in the vector with the id and start following the aux links.

  • If the next node is the last value then stop and resume iterating through the vector.

  • If the next value of the next node is 0, mark it with the id and continue following the aux link from there.

  • If the next value is not 0 and not the id you are currently using (you've reached a node you've already seen before) then stop and resume iterating throught the vector.

  • If the next value is the id you are using then you've found a cycle. Fix the aux pointer of the current node and resume iterating through the vector.

Overall this solution has a complexity of O(N) because you will visit each node at most twice.

Upvotes: 0

Related Questions