## 题目描述：

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.

## Python代码：

``````class Solution:
# @return a RandomListNode
nodeDict = dict()
dummy = RandomListNode(0)
while pointer:
newNode = RandomListNode(pointer.label)
while pointer:
if pointer.random:
return dummy.next
``````

```1. 遍历原链表，并复制每一个节点，将新节点插入原节点之后

2. 遍历新链表，为其中的新增节点设置random指针

3. 重建原链表，并提取出拷贝的新节点```

## C++代码：

``````public RandomListNode copyRandomList(RandomListNode head) {

// First round: make copy of each node,
// and link them together side-by-side in a single list.
while (iter != null) {
next = iter.next;

RandomListNode copy = new RandomListNode(iter.label);
iter.next = copy;
copy.next = next;

iter = next;
}

// Second round: assign random pointers for the copy nodes.
while (iter != null) {
if (iter.random != null) {
iter.next.random = iter.random.next;
}
iter = iter.next.next;
}

// Third round: restore the original list, and extract the copy list.

while (iter != null) {
next = iter.next.next;

// extract the copy
copy = iter.next;
copyIter.next = copy;
copyIter = copy;

// restore the original list
iter.next = next;

iter = next;
}

}
``````

Pingbacks已关闭。