题目描述
给定一个链表,每个结点包含一个额外增加的随机指针,该指针可以指向链表中的任何结点或空结点。
要求返回这个链表的 深拷贝。
我们用一个由 n
个结点组成的链表来表示输入/输出中的链表。每个结点用一个 [val, random_index]
表示:
val
:一个表示Node.val
的整数。random_index
:随机指针指向的结点索引(范围从0
到n-1
);如果不指向任何结点,则为null
。
样例
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]
输入:head = []
输出:[]
解释:给定的链表为空(空指针),因此返回 null。
限制
-10000 <= Node.val <= 10000
Node.random
为空(null
)或指向链表中的结点。- 结点数目不超过
1000
。
算法
(构造) $O(n)$
- 使用原地算法。
- 第一步,将新生成的结点放在原结点的后边,即
1 -> 1' -> 2 -> 2' -> NULL
。新结点的随机指针指向原结点。 - 第二步,扫描合成的链表,更新新结点的随机指针为原来指向结点的
next
。 - 第三步,将两个链表分离,恢复原链表,返回新链表的头结点。
时间复杂度
- 遍历三次链表,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外的空间。
C++ 代码
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node *copyRandomList(Node *head) {
if (!head)
return NULL;
Node *p = head;
while (p) {
Node *q = new Node(p->val, p->next, p->random);
p->next = q;
p = q->next;
}
p = head;
while (p) {
if (p->next->random)
p->next->random = p->next->random->next;
p = p->next->next;
}
p = head;
Node *newhead = head->next;
while (p) {
Node *q = p->next;
p->next = p->next->next;
p = p->next;
if (p)
q->next = p->next;
}
return newhead;
}
};
妙啊 ,这个想法溜到飞起, 不过代码我运行的时候有点问题,
我按照下面修改通过了:
第一个while循环改成:
第二个while循环里的:
在新的copy-list-with-random-pointer link中,修改后的代码如下:
这是因为牛客网上结点的构造函数不一样,所以得手动赋值。