C++/Creating a 'Y'-list from two std::list or std::forward_list objects
A colleague came across the frequently-asked C interview question "Imagine you have a singly-linked list L1 (of integers, for simplicity) with values 0 to 9. There is another singly-linked list L2 (again, of integers) with values 0 to 5. As expected, the next-pointers of the last nodes of both the lists point to NULL. Now, I modify the next-pointer of the last node of L2 to point to the 7th node of L1 (which has the integer 6 in it). We now have a 'Y' : two lists which merge into one. How would you find the node where the two lists merge?"
The problem is not difficult. However, my colleague came up with the question "How would one _create_ such a 'Y' from two std::list or two std::forward_list objects in C++?". The constraint is that one _must_ use the STL list/forward_list and other STL functions only. He can't figure it out and neither can I :-(
I agree that creating such a 'Y' would be inviting trouble but still, how would one do it if one wanted to? I tried to google for "combining/merging/joining multiple lists" but the usual answers (splice, std::move, etc) don't seem to help.
[UPDATE at end of original answer text]
TL;DR : Store pointers to the data objects in the list nodes rather than the data object values.
C++ standard library container types store data by value - that is they copy (or move or directly construct in C++11) objects that they store and the container then owns the (copied/moved/constructed) object.
Hence you cannot have the same object in two std::lists. You either have to make a copy from one list to the other or, since C++11 you have to move an object from one list to the other, invalidating the original (note: not all types are or should be movable).
Many other linked list implementations do not make copies of the object passed to the list for inclusion - they just store the object's pointer. You can probably see that with this type of list implementation you can easily create the 'Y' you were after.
Hence the way to replicate this using a std::list is to use a list of pointers to data objects: std::list<T*> rather than list<T>. However doing this using raw pointers leads to all sorts of problems. Firstly, std::list<> objects delete each node's object when the list is destroyed. However deleting a raw pointer does _not_ delete the object it points to so the list items need to be deleted manually before destroying the list. Secondly in this case as some nodes' data objects are going to be shared between lists - how do you know when to delete list items? Maybe a node is still used on one or more other lists.
Both problems can be taken care of by using a suitable smart pointer. In this case std::shared_pointer (for C++11 implementations) would be such a smart pointer type or std::tr1::shared_pointer for mid-naughties implementations or look at boost::shared_pointer if neither of the others two are available. In fact you should use the associated make_shared function to create objects referred to by a shared_pointer. You might wish to look up further information on smart pointers, such as:
A shared_pointer will keep a count of references to the pointer it manages, or rather the object it manages via its pointer. When the reference count goes to zero the object is deleted.
This solves both the problems mentioned above with std::list<T*>. A std::list<std::shared_pointer<T>> (or equivalent earlier/alternative of std::shared_pointer) will not require us to manually delete the object in the list and each shared pointer knows how many lists - and possibly other things - are referring to the pointed to object and will delete that object only when there is nothing left to refer to it.
Hope this helps.
UPDATED TO ADD:
It occurred to me a while after I posted my answer (and sorry some life stuff distracted me from getting this update out sooner!) that I did not make it clear that although using (smart) pointers will allow you to create a sort of Y-shaped effect you cannot do exactly as I think the question you were querying about implied as std::list (and in C++11 and later std::forward_list - a singly linked list type) will not let you mess around with their node data (i.e. the link pointers)* in the way the question was asking about. You will still have two distinct lists with distinct nodes, with nodes at the end of each list that just happen to have node-data that refers (points to) the same data. You can still manipulate the two lists separately so that the Y shape no longer exists or is changed.
* OK you could work out the node structure of a specific std::list implementation and do all sorts of under handed things to mess with a list's nodes - C++ only helps protect you from mistakes not malice!