本文简单的求解了一个链表深度拷贝的例子。
深拷贝和浅拷贝对应，浅拷贝是拷贝一引用，而深拷贝拷贝的不仅仅是引用，还包括引用所属的值，简单的说就是拷贝另一份。
题目：
深拷贝一个链表，链表除了含有next指针外，还包含一个random指针，该指针指向链表中的某个节点或者为空。
本题有两种思路，分别介绍下。
思路一：（图片来源于网络）
假设原始链表如下，细线表示next指针，粗线表示random指针，没有画出的指针均指向NULL：
构建新节点时，指针做如下变化，即把新节点插入到相应的旧节点后面：
代码：
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){
if(head == NULL) return NULL;
/*第一遍扫描:对每个结点进行复制，把复制出来的新结点插在原结点之后*/
RandomListNode* node = head;
while(node != NULL)
{
RandomListNode* newnode = new RandomListNode(node->label);
newnode->next = node->next;
node->next = newnode;
node = newnode->next;
}
/*第二遍扫描:根据原结点的random,给新结点的random赋值*/
node = head;
while(node != NULL)
{
if(node->random != NULL)
{
node->next->random = node->random->next;
}
node = node->next->next;
}
RandomListNode* newhead = head->next;
/*第三遍扫描:把新结点从原链表中拆分出来*/
inode = head;
while(node != NULL)
{
RandomListNode* newnode = node->next;
node->next = newnode->next;
if(newnode->next != NULL)
newnode->next = newnode->next->next;
node = node->next;
}
return newhead;
}
};
思路二：
该思路是利用两个HashMap来求解的，第一次遍历时：一个Map存放 旧值--新值 键值对、另一个Map存放 新值--旧值 键值对；第二次遍历时：将原链表中的random结点拷贝过来；看了代码就十分明了了。
代码：（java代码）
class Solution{
public RandomListNode copyRandomList(RandomListNode head)
{
if(head == null) return head;
/*新建一个链表的头结点*/
RandomListNode newHead = new RandomListNode(head.label);
RandomListNode oldp = head;
RandomListNode newp = newHead;
Map<RandomListNode,RandomListNode> map1 = new HashMap<RandomListNode,RandomListNode>();
Map<RandomListNode,RandomListNode> map2 = new HashMap<RandomListNode,RandomListNode>();
map1.put(newp,oldp);
map2.put(oldp,newp);
/*对旧链表进行复制*/
oldp = head->next;
while(oldp != null)
{
RandomListNode temp = new RandomListNode(oldp.label);
map1.put(temp,oldp);
map2.put(oldp,temp);
newp.next = temp;
newp = newp.next;
oldp = oldp.next;
}
/*将Random指针进行复制*/
newp = newHead;
while(newp != null)
{
newp.random = map2.get(map1.get(newp).random);
/*
map1.get(newp):
为新链表的结点对应旧链表中的旧结点;
map1.get(newp).random:
为旧结点的random;
map2.get(map1.get(newp).random):
为新结点的random;
上述等式成立是因为新结点的random与对应旧结点的random也互为键值对
*/
newp = newp.next;
}
return newHead;
}
};
至此，两种思路介绍完毕。
如果觉得《深度拷贝小解》对你有帮助，请点赞、收藏，并留下你的观点哦！
