给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
《剑指Offer》同题:面试题35. 复杂链表的复制
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == NULL)
return NULL;
unordered_map<Node*, Node*> m;//原节点-新节点 哈希表
Node *cur = head, *newNode;
while(cur != NULL)//先创建新节点,赋值
{
newNode = new Node(cur->val);
m[cur] = newNode;
cur = cur->next;
}
cur = head;
while(cur != NULL)//再次遍历,查表,把新节点指针付进去
{
m[cur]->next = m[cur->next];
m[cur]->random = m[cur->random];
cur = cur->next;
}
return m[head];
}
};
a ->a.-> b-> b.-> ...
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head)
return NULL;
Node* cur = head, *newNode, *H;
while(cur)//复制一遍原链表 a a` b b`...
{
newNode = new Node(cur->val);
newNode->next = cur->next;
cur->next = newNode;
cur = newNode->next;
}
cur = head;
newNode = cur->next;
while(cur)//把新链表的random接好
{
if(cur->random)
newNode->random = cur->random->next;
cur = cur->next->next;
if(cur)
newNode = cur->next;
}
cur = head;
H = newNode = cur->next;
while(newNode->next)//两条链表拆开
{
cur->next = newNode->next;
newNode->next = newNode->next->next;
cur = cur->next;
newNode = newNode->next;
}
cur->next = NULL;
return H;
}
};