Find the missing link Thee million men write down their name and the person to their left and the person on the far left throws out his paper.  Reconstruct the list.

A List takes a while. Don't try 3 million unless you have some time.

Up front we do NOT know the remaining man on left is 0.  That is what we are looking for. The remaining here is 0 as the was test data easy to create.

public static void TAOCPthreeMillionMenTest()
{
    int numberOfMen = 30000;  // test at less than 3 million or get killed
    List&lt;PairInt&gt; pairs = new List&lt;PairInt&gt;(numberOfMen);
    for (int i = 0; i &lt; numberOfMen; i++)
    {
        pairs.Add(new PairInt(i, i + 1));
    }
    // shuffle left
    Random rand = new Random();
    int temp;
    int j;
    //shuffl up
    for (int i = numberOfMen - 1; i &gt; 0; i--)
    {
        j = rand.Next(i + 1);
        if (i != j)
        {
            temp = pairs[i].Rght;
            pairs[i].Rght = pairs[j].Rght;
            pairs[j].Rght = temp;
            temp = pairs[i].Left;
            pairs[i].Left = pairs[j].Left;
            pairs[j].Left = temp;
        }
    }
    foreach (PairInt pair in pairs)
    {
        //Debug.WriteLine(pair.Left + " " + pair.Rght);
        if (pair.Left == pair.Rght)
            Debug.WriteLine("pair.Left == pair.Rght");
    }
    Debug.WriteLine("");
    Debug.WriteLine(TAOCPthreeMillionManLeft(pairs));
    Debug.WriteLine("");
}
public static int TAOCPthreeMillionManLeft(List&lt;PairInt&gt; pairs)
{
    List&lt;PairInt&gt; lineEmUp = new List&lt;PairInt&gt;();
    int lineEmUpCountMax = 0;
    int lineEmUpCountMaxCount = 0;
    PairInt matchRght;
    PairInt matchLeft;
    int count = 0;
    foreach (PairInt pair in pairs)
    {
        count++;
        //Debug.WriteLine("new   " + pair.Left + " " + pair.Rght);
        //foreach (PairInt exist in lineEmUp)
        //{
        //    Debug.WriteLine("exist " + exist.Left + " " + exist.Rght);
        //}
        //Debug.WriteLine("");
        matchRght = lineEmUp.FirstOrDefault(x =&gt; x.Rght == pair.Left);
        matchLeft = lineEmUp.FirstOrDefault(x =&gt; x.Left == pair.Rght);
        if (matchRght != null)
        {
            if (matchLeft != null)
            {
                matchRght.Rght = matchLeft.Rght;
                lineEmUp.Remove(matchLeft);
            }
            else
            {
                matchRght.Rght = pair.Rght;
            }
        }
        else if (matchLeft != null)
        {
            matchLeft.Left = pair.Left;
        }
        else
        {
            lineEmUp.Add(pair);
            if (lineEmUpCountMax &lt; lineEmUp.Count)
            {
                lineEmUpCountMax = lineEmUp.Count;
                lineEmUpCountMaxCount = count;
            }
            //Debug.WriteLine("lineEmUp.Count " + lineEmUp.Count);
        }
    }
    // lineEmUp should have only one entry
    if (lineEmUp.Count != 1)
    {
        Debug.WriteLine("");
        Debug.WriteLine("lineEmUp.Count != 1");
        foreach (PairInt pair in lineEmUp)
        {
            Debug.WriteLine(pair.Left + " " + pair.Rght);
        }
        Debug.WriteLine("");
    }
    return lineEmUp[0].Left;
}

public class PairInt
{
    public int Left { get; set; }
    public int Rght { get; set; }
    public PairInt(int left, int rght)
    {
        Left = left;
        Rght = rght;
    }
}


I tried a double dictionary but could not make it work.
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);
}