java - 为什么这个“用下一个随机指针克隆一个链表”的解决方案是 O(1) 空间复杂度？

问题描述

给定一个链表，每个节点都有两个指针。第一个指向链表的下一个节点，另一个指针是随机的，可以指向链表的任何节点。编写一个程序，在 O(1) 空间中克隆给定列表，即没有任何额外空间。

这里给出的答案：

在每个节点之间插入 copyNode。
然后将随机指针复制到 Original->next（即复制的）。

解决方案：

/**
 * 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;
    }
}

现在我看到副本正在创建新的额外空间。看起来像空间：O（N）。

有人可以解释为什么这是 Space: O(1) 吗？

标签： javadata-structureslinked-listbig-ospace-complexity

java - 为什么这个“用下一个随机指针克隆一个链表”的解决方案是 O(1) 空间复杂度？

问题描述

解决方案

推荐阅读