Почему это решение "Клонировать связанный список со следующим и случайным указателем" является O (1) Пространство сложности?

Question

Есть решение для вопроса «Клонировать связанный список со следующим и случайным указателем» в пространстве O (1).

Вопрос: задан связанный список, имеющий два указателя в каждом узле.Первый указывает на следующий узел списка, однако другой указатель является случайным и может указывать на любой узел списка.Напишите программу, которая клонирует заданный список в пространстве O (1), т. Е. Без дополнительного пространства.

Ответ, который он дает: Вставьте copyNode между каждым узлом.Затем скопируйте случайный указатель в Original-> next (который скопирован).

Решение Java Code:

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode cur = head;
        //insert copy in between nodes
        while(cur != null)
        {
            RandomListNode copy = new RandomListNode(cur.label);
            //1->1'->2
            copy.next = cur.next;
            cur.next = copy;
            cur = cur.next.next;
        }
        cur = head;
        //assign random to copy
        while(cur != null)
        {
            RandomListNode copy = cur.next;
            //random.next is the copy of random
            if(cur.random != null)
            {
                copy.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        RandomListNode dummy = new RandomListNode(0);
        cur = head;
        RandomListNode copyPre = dummy;

        while(cur != null)
        {
            RandomListNode copyNode = cur.next;
            //split and reconnect w/ original next node
            cur.next = copyNode.next;
            //connect the copied node
            copyPre.next = copyNode;
            copyPre = copyNode; //iterates copy
            cur = cur.next; //iterates
        }

        return dummy.next;
    }
}

Ссылка ответа: [здесь] https://www.geeksforgeeks.org/clone-linked-list-next-random-pointer-o1-space/

Теперь я вижу, что копией создается новое дополнительное пространство.Что выглядит как пробел: O (N).

Может кто-нибудь объяснить, почему это пробел: O (1)?