题目

Copy List with Random Pointer

思路

O(n),O(n) Map求解

这道题是复制一个链表，特殊的地方是，与一般的链表相比多一个random指针，随机指向链表中的任何一个节点，包括空与自身。那么主要是如何处理这样的一个随机指针。

由于是复制一个链表，因此需要复制每个节点，所以第一次遍历就需要做这个工作。同时引入Map的key-value机制，将原节点的地址与新开辟的对应节点的地址对应起来，这样做的好处就是在下一次遍历时，通过Map就能访问的新开辟节点的链表关系。

代码

#include <iostream>
#include <map>
using namespace std;
struct RandomListNode {
    int label;
    RandomListNode *next, *random;
    RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
};
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *copy = new RandomListNode(0);
        RandomListNode *p = head;
        RandomListNode *q = copy;
        map<RandomListNode*, RandomListNode*> Map;
        while(p != NULL){
            q -> next = new RandomListNode(p -> label);
            Map[p] = q -> next;
            q = q -> next;
            p = p -> next;
        }
        p = head;
        q = copy;
        while(p != NULL){
            q -> next -> random = Map[p -> random];
            p = p -> next;
            q = q -> next;
        }
        return copy -> next;
    }
};

在Leetcode的讨论中还看到了另一种更直观的使用HashMap的方法：

// m,n 初始时都指向head
//第一次遍历对HashMap进行赋值
while(m){
    Map[m] = new RandomListNode(p -> label);
    m = m -> next;
}
//第二次遍历直接赋值两个指针next与random
while(n){
    Map[n] -> next = Map[n -> next];
    Map[n] -> random = Map[n -> random];
    n = n -> next;
}