k-way merge but without an absolute order
I have k lists that I would like to combine to a single list. Each list's elements are unique and are sorted in a particular order, but there is no notion of an absolute order, and different items across lists can only be compared if they are equal. To give a specific example (here I use < to indicate the sorting inside each list):
l1 = a < b < c
l2 = b < d
l1 + l2 should result in one of the following (and I don't care which one it results in):
a < b < c < d
a < b < d < c
If the lists are incompatible, e.g. a < b and b < a then I want to get an error.
I thought about modifying k-way merge somehow but it's not clear to me how to do that without a global order. Btw, I'll probably be happy with a $O(nk)$ solution.
edit: sorry if it's not clear from above, but the resulting list (if it exists) should respect all of the orderings of the sublists. Also all the items should be unique in the result.
edit 2: Perhaps a better way to phrase the problem is this. I'd like to construct an order vector given k pieces of that order vector (or get an error if that's impossible).
Here's an algo that I think works for k=2. 864
Find and mark all the duplicates - I think this is $O(n)$ - then start writing down elements from first list until you hit a duplicate, once you do add all elements from second list until you hit that same duplicate, then write down the duplicate and continue. The part where it's a bit more tricky with k>2 is that the duplicate may not be in every list to do the above (and this process cannot be done sequentially, i.e. l1+l2+l3 is generally not the same as (l1+l2)+l3, where + denotes this operation of finding the superset order list).
final edit: Now that I thought a bit more about it, should be easy to extend the above to any k. Use a hash to find which lists each unique element belongs to. Then traverse along the first list using the above logic - writing down all elements until you hit first duplicate, in which case write down all elements (that haven't been written down yet) in all other lists before that duplicate and keep doing that until you reach the end of first list. If haven't reached the end of second list, continue same algo there and so on. Each list will be traversed twice - once to get the duplicates, and second time to do the above, making it $O(n)$. A compatibility error will be discovered if you iterate along a list but can't find the duplicate (because it was already written down in an earlier pass).
Please let me know if I missed something. 864