Concatenation of two circular linked lists

 Here is a trick question - a data structures question for you

Write a function to concat two circular linked lists. Without traversing either of them. The lists are singly linked.

hint : order is not important.

Let us try to understand the situation. We have two single linked circular lists. We have to join them. 

One easy solution would be to traverse to the end of first list and link the last node to second list. But we are not allowed to do that. 

The second possible solution could be find the previous node of head of first list - which will be last node. And then link it to second list. Again, not possible as the list is not doubly linked.

Ok. Here is the solution 

• Let temp be the next node of head of list1
• Link head of list1 to head->next of list2
• Link head of list2 to temp

Let us take an example.

Let the two lists be 

1-2-3-4-5

and

10-20-30

• Now let temp=2
• Assign  1->next =20.  Now we have list1 as 1-20-30-10. and back to 20
• Assign 10->next=temp.   Which is 2

So now the list1 is 1-20-30-10-2-3-4-5-1

You can find the complete C code here