Путать с пространственной сложностью следующего алгоритма

Question

Я смотрел на вопрос Ссылка , и это говорит о том, что пространственная сложность решения равна O (1) (прочитайте ответ по Макс ).Я сомневаюсь, что сложность пространства - это пространство, необходимое для алгоритма, и я правильно понял, и чувствую, что это определенно O (n), где n - размер связанного списка.Кто-нибудь может сказать, что это неправильный ответ или я ошибся в понимании?

Answer 1

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

Это видно из описания алгоритма:

Создайте копию узла 1 и вставьте ее между узлом 1 и узлом 2 в исходный связанный список, создайте копию 2 и вставьте ее между 2 и 3. Продолжайте таким же образом, добавьте копию N после N-гоblockquote узла

Здесь ответчик только что добавил "N" узлов, так что это по крайней мере O (n) сложность (и, действительно, пространственная сложность перечисленного алгоритма равна O (n)).