Удаление элементов по кругу

public static void RemoveEachSecondItem<T>(IEnumerable<T> ie)
    {
        ICollection<T> ic = new ICollection<T>(ie);
        while (ie.Count() > 1)
        {
            bool isOdd = false;//четный элемент
            foreach (var item in ic)
            {
                if (isOdd)
                {
                    ic.Remove(item);
                }
            }
        }
    }

"Честный" вариант решения

Алгоритм, по идее, прост:

• Cтроим кольцевой односвязный список (как упомянуто в комментарии @A K) по исходному перечислению (IEnumerable) элементов
• Пока элементов в построенном списке больше одного, идём по нему и удаляем каждый четный элемент
• Возвращаем единственный оставшийся в списке элемент

Реализация может получиться сложнее или проще... Пример:

Узел списка:

private class MyNode<T>
{
    public readonly T item;
    public MyNode<T> next;
    public MyNode(T item)
    {
        this.item = item;
    }
}

Построение списка по перечислению элементов:

• Храним ссылки на первый и предыдущий узлы
  • Ссылка на первый узел нужна для его особой обработки: мы не можем на первой итерации цикла последнему узлу проставить в качестве следующего первый (мы не знаем ещё ничего про последний узел), поэтому для этого по-особому обрабатываем первый узел в цикле и делаем недостающую связку "последний -> первый" после цикла
  • Ссылка на предыдущий узел нужна, чтобы на итерации цикла (кроме первой) предыдущему узлу в качестве следующего проставить текущий, тем самым создавая односвязный список с направлением "вперёд"
• Проходим по исходному перечислению, по-особому обрабатывая первый узел и проставляя связь между предыдущим и текущим для остальных узлов
• Закольцовываем список, указывая последнему элементу (после цикла previousNode как раз указывает на него) в качестве следующего первый
• Возвращаем первый узел - его достаточно для работы со списком

_

private static MyNode<T> CreateCircularList<T>(IEnumerable<T> ie)
{
    MyNode<T> firstNode = null;
    MyNode<T> previousNode = null;
    foreach (var item in ie)
    {
        var newNode = new MyNode<T>(item);
        if (firstNode == null)
        {
            firstNode = newNode;
        }
        else
        {
            previousNode.next = newNode;
        }
        previousNode = newNode;
    }
    previousNode.next = firstNode;
    return firstNode;
}

Непосредственно само удаление элементов:

• Считаем пустое перечисление элементов недопустимым вариантом
• Создаём список и получаем ссылку на первый узел
• Создаём флаг (isOdd), отвечающий за удаление каждого второго узла (== true - удалять, == false - нет)
• В качестве текущего (рассматриваемого) узла первоначально берём первый
• Ссылка на предыдущий узел нужна для "склеивания" предыдущего и следующего при удалении текущего
• Пока узлов в списке больше одного:
  • Если узел нужно удалить (он второй/"четный") - склеиваем предыдущий со следующим, тем самым исключая текущий узел из списка, и уменьшаем счетчик количества узлов в списке на единицу
  • Иначе в качестве предыдущего узла устанавливаем текущий, плавно готовясь к следующей итерации цикла, в которой этот самый предыдущий узел понадобится для "склеивания"
  • После чего переходим к следующему узлу и меняем значение флага
• В итоге возвращаем значение единственного оставшегося узла

_

public static T RemoveEachSecondItem<T>(IEnumerable<T> ie)
{
    var elementsCount = ie.Count();
    if (elementsCount == 0)
        throw new Exception("Empty ie");
    var firstNode = CreateCircularList(ie);
    var isOdd = false;
    var currentNode = firstNode;
    MyNode<T> previousNode = null;
    while (elementsCount > 1)
    {
        if (isOdd)
        {
            previousNode.next = currentNode.next;
            elementsCount--;
        }
        else
        {
            previousNode = currentNode;
        }
        currentNode = currentNode.next;
        isOdd = !isOdd;
    }
    return currentNode.item;
}

"Нечестный" вариант решения

• Посчитать сразу индекс элемента, который останется. Доказательства приведённой формулы (из количества элементов вычитаем ближайшую снизу степень двойки, после чего разность умножаем на два - получаем нужный индекс) у меня нет, но она работает
• Вернуть элемент по этому индексу. Из-за условий задачи для этого придётся воспользоваться foreach-ем

Пример:

public static T RemoveEachSecondItemShort<T>(IEnumerable<T> ie)
{
    var elementsCount = ie.Count();
    var powOfTwo = 1;
    while (powOfTwo <= elementsCount)
    {
        powOfTwo <<= 1;
    }
    powOfTwo >>= 1;
    var requiredElementIndex = (elementsCount - powOfTwo) * 2;
    var index = 0;
    foreach (var element in ie)
    {
        if (index == requiredElementIndex)
            return element;
        index++;
    }
    throw new Exception("Empty ie");
}

1. Вам в код(в цикл foreach) нужно добавить изменение переменной isOdd, ибо сейчас это выглядит как просто foreach, в котором никогда не вызывается Remove.

Сейчас он: isOdd == false постоянно. Когда мы в foreach делаем if(isOdd == true), это никогда не произойдет

Как можно сделать: Сначала он true(при инициализация. В начале цикла он меняется на противоположный(получается первый элемент нечетный, а второй четный. И таким образом происходит переключение).

2. while (ie.Count() > 1)

что вы хотите получить от этого куска кода? ie.Count() будет возвращать одно и то же, ибо когда вы делаете это ICollection<T> ic = new ICollection<T>(ie); вы получаете копию, а не работаете с той же коллекцией

В итоге когда закончится цикл foreach, вы выйдете в цикл while иии... он будет крутится вечно). Если я правильно понял идею, вам нужно заменить while (ie.Count() > 1) на while (ic.Count() > 1)

3. ICollection<T> ic = new ICollection<T>(ie); нельзя создавать объект интерфейса. Ибо интерфейс - лишь декларация, описание того как можно работать с чем то. Он не имеет ни строчки реализации и не может. Вы можете создать(инстанцировать) только объект определенного класса.

Например ICollection<T> ic = new List<T>(ie);

тут мы говорим, что я создаю объект класс List<T>, но работать с ним буду через интерфейс ICollection<T>.

4. Вы не можете изменять коллекцию внутри цикла foreach(спасибо @aa_talanin. Как я такое мог забыть). Используйте не foreach, а цикл for. Но т.к. нельзя использовать цикл for...Стоит записывать элементы, который вы хотите удалить в отдельный список, а потом в цикле делать Remove из первой коллекции.

По сути ваша задача — "Считалка Иосифа Флавия"

И если у нас на входе N элементов, то нужно найти такое максимальное целое A, чтобы N = 2A+L, где L ⩾ 0. Тогда результатом будет элемент под индексом 2L (индексы с 0).

Поскольку, по условию на входе могут быть List<T> или LinkedList<T>, которые реализуют ICollection<T>, можно написать такое простое решение:

T FlaviusRoulette<T>(ICollection<T> source)
{
    int c = source.Count, n = 0;
    while (1 << n <= c) ++n;
    return source.ElementAt(2 * c - (1 << n));
}

Если же вы хотите, чтобы метод работал для любых IEnumerable<T> — выхода нет, придется закешировать все элементы, т. к. любой может оказаться ответом:

T FlaviusRoulette<T>(IEnumerable<T> source)
{
    var col = source as ICollection<T> ?? source.ToList();
    int c = col.Count, n = 0;
    while (1 << n <= c) ++n;
    return col.ElementAt(2 * c - (1 << n));
}

Проверка:

Console.WriteLine(FlaviusRoulette(Enumerable.Range(1, 41))); // 19

Проверку source == null и source.Count == 0 оставляю на ТС.

Можно пожертвовать памятью и получить быстрое и довольно простое решение:

T RemoveEachSecondItem<T>(IEnumerable<T> source)
{
    List<T> src = source.ToList();
    List<T> tgt = new List<T>(src.Count / 2);   
    foreach(var item in source)
        src.Add(item);
    bool isRemoved = false;
    while(src.Count > 1)
    {
        foreach(T item in src)
        {
            if(!isRemoved)
                tgt.Add(item);
            isRemoved = !isRemoved;
        }
        List<T> temp = src;
        src = tgt;
        tgt = temp;
        tgt.Clear();
    }
    return src.FirstOrDefault();
}
//Пример использования
Console.WriteLine(RemoveEachSecondItem<int>(Enumerable.Range(1, 7), false));

Достоинства:

• работать будет с любым перечислением.
• хорошо оптимизируется для эффективного использования кэша процессора, за счет использования линейных массивов, на которых строится List<T>.

Недостатки:

• дополнительный расход памяти (N*2,5+x с учетом хранения исходных данных входного перечисления или N*1,5+x, если исходные данные не хранятся в памяти процесса, а генерируются например, где x - разница между реальной и используемой емкостями src)
• при материализации перечисления будет происходить постепенное увеличение емкости src со всеми вытекающими накладными расходами.