Цитата
Чтоб можно было оптимизировать, надо знать, что для тебя - НЕоптимизированный вариант.
НЕ оптимизированный вариант очевиден - перестановка участка списка. Выполняется за постоянное время. Недостаток, очевидно, необходимость переброски итераторов на начало и конец переставляемого участка.
Смущает простота лобового решения задачи.
Цитата
Кстати. Зачем это оптимизировать? Ты не привел никаких временнЫх ограничений, и ограничений по памяти тоже не привел, кстати...
Если б я их знал, то, очевидно привел бы.
Цитата
Без оптимизации: однонаправленный список + последовательный поиск элемента с нужным номером + перестановка 4-х указателей при перемещении блока в начало списка. На 100 тысячах элементов и 25 тысячах перестановок отрабатывает за 1.5 секунды. Двунаправленный список будет пожирать больше памяти, но может сэкономить время на нахождение элементов списка, расположенных ближе к его концу, чем к началу...
Радует, по крайней мере, что направление мысли было правильным. ??? Т.е. из двунаправленного списка я и исходил. Плюс примитивная оптимизация по месторасположению участка (конец-начало списка). Наверное, возможен анализ по сопоставлению участка с промежуточным итератором...
Жаль, что правильность решения можно оценить только после удачной сдачи.