给定一个链表，每个节点有两个指针。第一个指针指向列表的下一个节点，另一个指针是随机的，可以指向列表的任何节点。编写一个程序，在 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(。
有人能解释为什么这是空间：O(1(吗？
除了原始源数据 (o(n(( 和结果数据(也是 o(n((，该算法仅使用 o(1( 辅助数据。