Implement an algorithm to insert a node into a circular linked list without traversing it

Question

I was thinking of a solution to this problem.

My input:
1. Have a tail pointer which points to the last node.
2. Once you know the last pointer you can easily add a new node next to it.

Void Insert(Node N)
{  
    if (head == null) // linked list is empty
    {
       head = N; tail = N; tail.Next = head;
    } 
    else
    {        
      Node temp = tail.Next; // since this is circular tail will point to head
      Tail.Next = N;
      N.Next = temp; // correct 
      tail = N;       
    }
}

Can any1 think of better solution without using tail pointer? Also as stated in problem without traversing? This is an interview question, just need some inputs to find the best solution.

Answer 1

I guess that you have a singly linked circular list, and only a pointer to one element (call this the head node). Each node of the list thus consists of a value and a pointer to the next element. The tail node points to the head node. Inserting a node directly after the head node is trivial. I guess that you want to insert a node directly before the head node. For that, you need the new node to become the last node, which is pointed to from the former last node, and which points to the head node. Now, you want to avoid traversing the list to find the last node. This means that you cannot access that last node and thus, not modify its pointer. The only other way to make this work is to modify the place that last node points to, i.e.:

1. insert a new node after the head node
2. copy the current head node's value to that new node
3. put the new value into the current head node
4. make the new node the new head node

Answer 2

you also have the head node. you can insert using it too. I am assuming there is no restriction on where to insert the new node (question doesnt explicitly specify that).

Inserting it on head is trivial.

Edit Insert it after the head