138.md

Copy List with Random Pointer

题目

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.

思路

遍历一边原链表，对于每一个结点A copy一个新结点B出来， 建立一个map<pointer,pointer> mp; 建立对应A--B。

生成一个mp 原链表的每一个结点都对应一个 新的结点。 一个与语句建立random指针.

在遍历一边链表，指向每一结点的指针为cur 则： mp[cur]->random = mp[cur->random]。

代码

/**
 * 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) {
        map<RandomListNode *,RandomListNode *> mp;
        if(!head) return nullptr;
        RandomListNode * new_head=new RandomListNode(*head);
        RandomListNode * last = new_head;
        RandomListNode * head_copy = head;
        mp[head_copy] = new_head;
        head_copy = head_copy->next;
        while(head_copy){
            RandomListNode * temp = new RandomListNode(*head_copy);
            mp[head_copy] = temp;
            last->next = temp;
            last = last->next;
            head_copy = head_copy->next;
        }
        head_copy = head;
        while(head_copy){
            mp[head_copy]->random = head_copy->random==nullptr? nullptr:mp[head_copy->random];
            head_copy = head_copy->next;
        }
        return new_head;
        
    }
};