完整教程：leetcode_138 随机链表的复制

1. 题意

就是复制链表，不过链表多了一个random指针，

它随机的指向链表中的元素，或者是一个空值。

2. 题解

如果是普通的链表，我们直接复制就好了，不过多了一个随机指针，它有可能指向后面的元素，因此我们可以用一个哈希表进行记录。

2.1 哈希表

有两种写法，一种是递归的。就是官方说的回溯。

class Solution
{
public:
unordered_map<Node*, Node*> cachedNode;Node* copyRandomList(Node* head) {if (head == nullptr) {return nullptr;}if (!cachedNode.count(head)) {Node* headNew = new Node(head->val);cachedNode[head] = headNew;headNew->next = copyRandomList(head->next);headNew->random = copyRandomList(head->random);}return cachedNode[head];}};

另外一种是迭代的写法

/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution
{
public:
Node* copyRandomList(Node* head) {
Node *nHead = NULL;
Node *pre = NULL;
map<Node *, Node *> pr;pr[NULL] = NULL;for (Node *cur = head; cur != NULL; cur = cur->next) {Node *ncur = new Node(cur->val);pr[cur] = ncur;if ( pre == NULL) {nHead = ncur;}else {pre->next = ncur;}pre = ncur;}for (Node *cur = head; cur != NULL; cur = cur->next ) {pr[cur]->random = pr[cur->random];}return nHead;}};

2.2 奇偶链表

这种解法是在0x3f的题解里面看到的，

我自己感觉跟哈希表其实是一样的，

只是这里取了一下巧。

具体做法就是，把每一个复制的链表节点给链接到老链表的后面。

这样其实就可以通过next来实现和哈希表一样的功能了！

最后再把链表给断开就好了。

class Solution
{
public:
Node* copyRandomList(Node* head) {
Node *nxt = NULL;
for (Node * cur = head; cur != NULL; cur = nxt) {
nxt = cur->next;
Node *nNode = new Node(cur->val);
cur->next = nNode;
nNode->next = nxt;
}
for (Node *cur = head; cur != NULL; cur = cur->next->next) {
if ( cur->random != NULL) {
cur->next->random = cur->random->next;
}
}
Node *nHead = NULL;
if (head)
nHead = head->next;
for (Node *cur = head; cur != NULL && cur->next != NULL; cur = nxt ) {
nxt = cur->next;
cur->next = nxt->next;
}
return nHead;
}
};

3. 参考

leetcode
0x3f