Algorithm for quickly obtaining a partial ordering over multiple linked lists

Question

I have a situation, as follows:

• I have n doubly-linked lists
• Each list has a sentinel beginning and end
• The lists all have the same beginning and end node (not required, but for simplicity's sake)
• The lists are homogenous and may share items

I'd like to find a partial ordering of all nodes in all n lists, starting with the beginning node and ending with, well, the end node, such that any node which appears in n-x lists, where x < n, will be sorted with respect to the other nodes in all the lists in which it appears.

Using arrays to provide an example set of lists:

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 admissible ordering would be [a, b, d, e, c, f, g, h, i].

I know that there is a fast algorithm to do this, does anybody remember how it goes or what it is called? I already have a few slow versions, but I'm certain that somewhere in Knuth there is a far faster one.

(And, before you ask, this is not for homework or Project Euler, and I cannot make this any more concrete. This is the problem.)

Edit: I am relatively sure that the partial ordering is defined only as long as the endpoints are in all of the lists and in the same positions (beginning and end). I would not be against a linear-time search to find those endpoints, and if they can't be found, then an error could be raised there.

Answer 1

Looks very similar to Topological sort to me. There's several algorithms to get you a topologically sorted state. The one I particularly like is similar to a breadth first search. Maintain two lists, one of all nodes which have no in-edges, say L (initially just the a node), the other with the 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 "do some operations step",

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, the list F has all your nodes topologically sorted. I'm sorry about the awful explanation, the wiki link has nice diagrams :)