# Copy List with Random Pointer

## Question

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 - 哈希表(两次遍历)

|------------|             |------------|
|            v       ===>  |            v
1  --> 2 --> 3 --> 4       1' --> 2'--> 3'--> 4'


1. 根据 next 指针新建链表
2. 维护新旧节点的映射关系
3. 拷贝旧链表中的 random 指针
4. 更新新链表中的 random 指针

### Python

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
# @return: A RandomListNode
dummy = RandomListNode(0)
curNode = dummy
randomMap = {}

# link newNode to new List
curNode.next = newNode
# map old node head to newNode
# copy old node random pointer
#
curNode = curNode.next

# re-mapping old random node to new node
curNode = dummy.next
while curNode is not None:
if curNode.random is not None:
curNode.random = randomMap[curNode.random]
curNode = curNode.next

return dummy.next


### C++

/**
* 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:
/**
* @return: A new head of a deep copy of the list.
*/
if (head == NULL) return NULL;

RandomListNode *dummy = new RandomListNode(0);
RandomListNode *curNode = dummy;
unordered_map<RandomListNode *, RandomListNode *> randomMap;
// link newNode to new List
curNode->next = newNode;
// map old node head to newNode
// copy old node random pointer

curNode = curNode->next;
}

// re-mapping old random node to new node
curNode = dummy->next;
while (curNode != NULL) {
if (curNode->random != NULL) {
curNode->random = randomMap[curNode->random];
}
curNode = curNode->next;
}

return dummy->next;
}
};


### Java

/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @return: A new head of a deep copy of the list.
*/
if (head == null) return null;

RandomListNode dummy = new RandomListNode(0);
RandomListNode curNode = dummy;
HashMap<RandomListNode, RandomListNode> randomMap = new HashMap<RandomListNode, RandomListNode>();
// link newNode to new List
curNode.next = newNode;
// map old node head to newNode
// copy old node random pointer
//
curNode = curNode.next;
}

// re-mapping old random node to new node
curNode = dummy.next;
while(curNode != null) {
if (curNode.random != null) {
curNode.random = randomMap.get(curNode.random);
}
curNode = curNode.next;
}

return dummy.next;
}
}


### 源码分析

1. 只需要一个 dummy 存储新的拷贝出来的链表头，以用来第二次遍历时链接 random 指针。所以第一句异常检测可有可无。
2. 第一次链接时勿忘记同时拷贝 random 指针，但此时的 random 指针并没有真正“链接”上，实际上是链接到了原始链表的 node 上。
3. 第二次遍历是为了把原始链表的被链接的 node 映射到新链表中的 node，从而完成真正“链接”。

## 题解2 - 哈希表(一次遍历)

### Python

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
# @return: A RandomListNode
dummy = RandomListNode(0)
curNode = dummy
hash_map = {}

# link newNode to new List
else:
curNode.next = newNode
# map old node head to newNode
# copy old node random pointer
else:
#
curNode = curNode.next

return dummy.next


### C++

/**
* 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:
/**
* @return: A new head of a deep copy of the list.
*/
RandomListNode *dummy = new RandomListNode(0);
RandomListNode *curNode = dummy;
unordered_map<RandomListNode *, RandomListNode *> hash_map;
// link newNode to new List
RandomListNode *newNode = NULL;
} else {
}
curNode->next = newNode;
// re-mapping old random node to new node
} else {
}
}

curNode = curNode->next;
}

return dummy->next;
}
};


### Java

/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @return: A new head of a deep copy of the list.
*/
RandomListNode dummy = new RandomListNode(0);
RandomListNode curNode = dummy;
HashMap<RandomListNode, RandomListNode> hash_map = new HashMap<RandomListNode, RandomListNode>();
// link newNode to new List
RandomListNode newNode = null;
} else {
}
curNode.next = newNode;
// re-mapping old random node to new node
} else {
}
}
//
curNode = curNode.next;
}

return dummy.next;
}
}


## 题解3 - 间接使用哈希表

|------------|
|            v
1  --> 2 --> 3 --> 4


|--------------------------|
|                          v
1  --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
|                   ^
|-------------------|


|--------------------------|
|                          v
1  --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
|                         ^
|-------------------------|


### Python

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
# @return: A RandomListNode
return None

# step1: generate new List with node
while curr is not None:
newNode = RandomListNode(curr.label)
newNode.next = curr.next
curr.next = newNode
curr = curr.next.next

# step2: copy random pointer
while curr is not None:
if curr.random is not None:
curr.next.random = curr.random.next
curr = curr.next.next
# step3: split original and new List
while curr is not None:
newNode = curr.next
curr.next = curr.next.next
if newNode.next is not None:
newNode.next = newNode.next.next
curr = curr.next



### C++

/**
* 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:
/**
* @return: A new head of a deep copy of the list.
*/
if (head == NULL) return NULL;

// step1: generate new List with node
while (curr != NULL) {
RandomListNode *newNode = new RandomListNode(curr->label);
newNode->next = curr->next;
curr->next = newNode;
//
curr = curr->next->next;
}
// step2: copy random
while (curr != NULL) {
if (curr->random != NULL) {
curr->next->random = curr->random->next;
}
curr = curr->next->next;
}
// step3: split original and new List
while (curr != NULL) {
RandomListNode *newNode = curr->next;
curr->next = curr->next->next;
curr = curr->next;
if (newNode->next != NULL) {
newNode->next = newNode->next->next;
}
}

}
};


### Java

/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @return: A new head of a deep copy of the list.
*/
if (head == null) return null;

// step1: generate new List with node
while (curr != null) {
RandomListNode newNode = new RandomListNode(curr.label);
newNode.next = curr.next;
curr.next = newNode;
//
curr = curr.next.next;
}
// step2: copy random pointer
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// step3: split original and new List
while (curr != null) {
RandomListNode newNode = curr.next;
curr.next = curr.next.next;
curr = curr.next;
if (newNode.next != null) {
newNode.next = newNode.next.next;
}
}

}
}