and the algorithm is...

I don't even need to write pseudocode for my answer, because the algorithm has a name.

Topological sort! I can't believe I stared at this for so long and didn't see it.
Put each user list into a graph, with edges in list L from user L_i to user L_i+1, and then use topo sort.
Topo sort¹ is O(v+e). I think dan_erat's answer (the only person who submitted one, too) would work but it looks slow.

This could make a fun interview question because there's two sides to it: there is recognizing that the problem of representing the merged posets is a graph, and then on top of that knowing topological sort. But for weaker / less theory-heavy candidates you can see how well they do with manual solutions. And I like it 'cause it's actually a real problem. I'll implement it later, maybe tomorrow, and tell you what I find.


1 I admit I looked this one up to be sure I wasn't missing something, though it's obvious if you think for a sec.