An algorithm for quickly getting partial ordering across multiple linked lists

Question

I have the following situation:

• I have n doubly linked lists
• Each list has a start and end time zone.
• All lists have the same start and end node (not required, but for simplicity)
• Lists are homogeneous and can share items.

I would like to find a partial order of all nodes in all n lists, starting from the beginning of a node and ending, well, the end of a node, so that any node that appears in nx lists, where x <n, will be sorted relative to other nodes in all the lists in which it is displayed.

Using arrays to provide a set of sets of examples:

first = [a, b, d, f, h, i]; second = [a, b, c, f, g, i]; third = [a, e, f, g, h, i]; 

Obviously, one possible answer would be [a, b, c, d, e, f, g, h, i], but another valid order would be [a, b, d, e, c, f, g, h, i ].

I know that there is a quick algorithm for this, does anyone remember how it goes or what it is called? I already have some slow versions, but I'm sure somewhere in Knut there is a lot faster.

(And before you ask, this is not for homework or Project Euler, and I cannot make it more specific. This is a problem.)

Edit: I am sure that partial ordering is determined only as long as the endpoints are in all lists and in the same positions (start and end). I would not mind searching in linear time to find these endpoints, and if they cannot be found, then an error may be raised.

Answer 1

It looks very similar to the topological view for me. There are several algorithms to get a topologically sorted state. The one I especially like looks like the first width search. Maintain two lists, one of all nodes that have no boundaries says L (initially only a node), and the other with partial ordered nodes, F Now at every step

 pick a node from `L`, do some operations (explained later), and move the chosen node to the `F` list. 

In the "perform some operations" section

 choose all successors of the source node which have exactly one in-link add them to L. Remove the link from the source node to all the successors in the previous step 

Now in the list F all nodes are topologically sorted. Sorry for the terrible explanation, the wiki link has good diagrams :)

Answer 2

Either I'm wrong, or the alienhard algorithm may fail. (I would add this as a comment, but I'm too new to comment here.)

Consider the following example:

 first = [a, b, c, d, i]; second = [a, d, e, f, i]; third = [a, f, g, h, i]; 

Allenhardt algorithm will give: a=0, b=1, c=2, d=3, e=2, f=3, g=2, h=3, i=4 .

The algorithm then requires that e begin with d, although e followed d in the second.