Ответ 1
Совершенно можно сделать эту работу. На самом деле, существует только одно изменение, которое вам нужно сделать для алгоритма с двойным связыванием, чтобы заставить его работать.
Проблема с ситуацией с односвязным списком заключается в том, что если у вас есть указатель на середину списка, вы не можете вернуться назад, чтобы вернуться в первую четверть списка. Однако, если вы думаете об этом, вам не нужно начинать с середины, чтобы сделать это. Вместо этого вы можете начать с начала списка и пройтись до первой четверти. Это занимает (по существу) столько же времени, сколько и раньше: вместо перехода назад на n/4 шага вы можете начать с фронта и идти вперед n/4 шага.
Теперь предположим, что вы сделали первый шаг и находитесь в позиции n/4 или 3n/4. В этом случае у вас будет такая же проблема, как и раньше, если вам нужно вернуться в позицию n/8 или позицию 5n/8. В случае, если вам нужно попасть в позицию n/8, вы можете начать в начале списка и пропустить n/8 шагов. Что относительно случая 5n/8? Вот трюк - если у вас все еще есть указатель на точку n/2, вы можете начать там и пройти вперед n/8 шагов, что приведет вас в нужное место.
В общем случае вместо сохранения указателя на середину списка, сохраните два указателя в списке: один в начале диапазона, где это значение может быть, и один в середине диапазона, где это значение может быть, Если вам нужно переместиться вперед в списке, обновите указатель до начала диапазона, указав его на середину диапазона, затем проведите указатель до середины диапазона вперед на полпути до конца диапазона. Если вам нужно продвинуться назад в списке, обновите указатель до середины диапазона, указав указатель на переднюю часть диапазона, затем переходите вперед на полпути.
В целом, это то же сложное время, что и двусвязный случай: мы берем n/2 шага, затем n/4 шага, затем n/8 шагов и т.д., которые суммируются до O (n) всего шаги. Мы также производим только O (log n) общие сравнения. Единственное отличие - лишний указатель, который нам нужно отслеживать.
Надеюсь, это поможет!