LeetCode || Copy List with Random Pointer
2023-09-27 14:27:21 时间
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
思路1:最傻瓜的方法是首先遍历一次建立next关系的新list。然后第二次遍历处理random关系,对于每个有random结点的node,我们都从表头開始遍历寻找其random的结点。然后给新list的相应结点赋值。这种话对于每个node,寻找random须要花费O(N)时间。故总时间复杂度为O(N^2)。这个方案会超时。
思路2:改进思路1。假设处理random关系的复制,使其复杂度降为O(N)?答案是要找到原node的random指向的结点在新list中相应的那个结点,假设能一下找到,那么就攻克了;实现方法是使用一个map<old, new>。记录原node与新node的相应关系。然后进行两次遍历,第一次建立next关系的新list。第二次给新list建立random指向关系;代码例如以下:
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
map<RandomListNode *, RandomListNode *> mapNodes;
RandomListNode *newList = NULL;
RandomListNode *newHead = NULL;
RandomListNode *p = head;
if(head==NULL)
return NULL;
while(p!=NULL){
RandomListNode *q = new RandomListNode(p->label);
mapNodes[p] = q;
if(newHead==NULL){
newHead = q;
newList = q;
}
else{
newList->next = q;
newList = newList->next;
}
p = p->next;
}
p = head;
newList = newHead;
while(p!=NULL){
if(p->random!=NULL)
newList->random = mapNodes[p->random]; //注意这里要用p->random而不是p
p = p->next;
newList = newList->next;
}
return newHead; //返回值是newHead而不是newList,由于此时newList指向尾部
}
};
思路3:思路2没有改变原list结构,可是使用了map,故须要额外的内存空间,假设原list解构可变。那么能够不必使用map记录映射关系,而是直接把复制的node放在原node的后面,这样结构变为:
上面为第一次遍历,第二次遍历时把红色的新node的random域赋值。规则是:
newNode->ranodm = oldNode->random->next;
然后第三次遍历把上面的链表拆分为两个就可以。代码例如以下:
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *newList = NULL;
RandomListNode *newHead = NULL;
RandomListNode *p = head;
if(head==NULL)
return NULL;
while(p!=NULL){
RandomListNode *q = new RandomListNode(p->label);
q->next = p->next;
p->next = q;
p = q->next;
}
p = head;
while(p!=NULL){
if(p->random != NULL)
p->next->random = p->random->next;
p = p->next->next;
}
p = head;
while(p!=NULL && p->next!=NULL){ //注意这里的条件,首先要推断p是否为null
if(p==head){
newHead = p->next;
newList = newHead;
}
else{
newList->next = p->next;
newList = newList->next;
}
p->next = newList->next;
p = p->next;
}
return newHead; //返回值是newHead而不是newList,由于此时newList指向尾部
}
};
參考链接:http://www.2cto.com/kf/201310/253477.html
相关文章
- 【LeetCode】最长递增子序列 [M](动态规划)
- [leetcode]Rotate List
- LeetCode_回溯_中等_698.划分为k个相等的子集
- LeetCode·每日一题·1042. 不邻接植花·模拟
- LeetCode·每日一题·907.子数组的最小值之和·动态规划
- LeetCode·518.零钱兑换·动态规划
- LeetCode·199·二叉树的右视图·层次遍历
- LeetCode·93.复原IP地址·递归+回溯+剪枝
- ★ Linked List Cycle II -- LeetCode
- 【LeetCode】【Python】Linked List Cycle
- LeetCode——Rotate List
- leetcode先刷_Remove Duplicates from Sorted List II
- 「LeetCode合集」链表(List)及经典问题
- [LeetCode] 86. Partition List 划分链表
- [LeetCode] 61. Rotate List 旋转链表
- [LeetCode] 460. LFU Cache 最近最不常用页面置换缓存器
- [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点
- [LeetCode] 142. Linked List Cycle II 链表中的环 II
- [LeetCode] 242. Valid Anagram 验证变位词
- [LeetCode] 92. Reverse Linked List II 反向链表II
- leetcode 844 比较含退格的字符串
- leetcode 113 路径总和II
- leetcode 714 买卖股票的最佳时机含手续费