Копирование односвязного линейного списка

Дан список, каждый узел которого в качестве данных имеет другой указатель на узел, причем известно, что он указывает на какой-то элемент того же списка. Требуется построить копию данного списка, в которой дополнительный указатель на узел («данные») указывает на узел копии с тем же номером в копии, с каким указатель в оригинале для данного узла указывал на элемент исходного списка (за линейное время, на константной памяти, кроме заведения копий узлов).

Можете дать подсказку того в каком направлении думать? Непонимание реализации именно в этом:

узел которого в качестве данных имеет другой указатель на узел, причем известно, что он указывает на какой-то элемент того же списка

1

Односвязный список состоит из узлов, причём каждый узел является парой из ссылки на следующий узел и данных.
В рассматриваемой задаче вторая компонента узла (данные) также является указателем, причём то, на что он указывает, во всех случаях также является узлом некоторого списка.
Проще говоря, в этой задаче узел - это пара из двух указателей, а все рассматриваемые указатели указывают исключительно на какие-то узлы.

Односвязный список есть первый его узел. Рекурсивно определяется множество узлов списка. Каждый узел состоит из двух указателей. Один из них указывает на "следующий" узел. А второй...

Сообщение от Volobuev Ilya узел которого в качестве данных имеет другой указатель на узел, причем известно, что он указывает на какой-то элемент того же списка

указывает на какой-то узел этого же списка. Может, на себя. Может, на следующий. Может, на первый.

Насколько я понимаю, стоит задача создать другой список, множество узлов которого было бы равномощным (взаимооднозначно соответствующим) исходному. Обе ссылки каждого узла A нового списка должны указывать на узлы нового списка, соответствующие узлам старого списка, на которые указывают указатели узла-праобраза A старого списка.

Все остальные обсуждения, как мне кажется, следует сопровождать иллюстрациями с двумя изоморфными непересекающимися графами узлов. Рисуйте.

1

Mysterious Light, я думаю что при создании копии списка следует где то хранить ссылки (которые лежат в информационных полях узлов списка). Только вот где и как...

0

делаешь в два шага
1) создать список того же размера но с пустым полем данных
2) делаешь двойной цикл прохода по двум очередям одновременно, в первом цикле берешь данные из ячейки первой очереди, во втором цикле находишь куда ссылка из данных указывает и записываешь соответствующую ссылку в данные в ячейке второй очереди.

1

wingblack, не списки, а именно очереди?

0

Сообщение от Volobuev Ilya wingblack, не списки, а именно очереди?

Ошибся, списки конечно.

1