Find the missing link
Not sure if I get the problem, but one solution for reconstructing the original list (even 3.000.000 items) with a dictionary is:

public static void ReconstructList(List&lt;PairInt&gt; pairs)
{
    var leftRightDict = pairs.ToDictionary(p =&gt; p.Left, p =&gt; p.Rght);   
    var idx = 0;
    while (leftRightDict.TryGetValue(idx, out idx)) 
        Console.WriteLine(idx);
}




Update:

The following code gets the ID of the left-most men:

public static void ReconstructList(List&lt;PairInt&gt; pairs)
{
    var rightLefttDict = pairs.ToDictionary(p =&gt; p.Rght, p =&gt; p.Left);
    // just start with any men
    var right = pairs[0].Rght;
    while (rightLefttDict.TryGetValue(right, out right)) {}
    Console.WriteLine(right);
}