剑指offer-复杂链表的复制

本文为剑指 offer 系列第二十七篇。
主要知识点为链表，同样是先遍历后操作，本来有只有一个后继结点，现在多加一个random结点。

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

首先按照正常的链表的遍历将这个链表进行一次深度复制（正常遍历指的就是通过next指针进行遍历），
注意在复制的过程中通过一个map来保存原结点和新节点的对应关系，
然后再遍历一遍，将新链表中random的链接关系补充上。
整个题目就可以得到解决。

解题代码

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* head)
    {
       if(!head) return NULL;
       unordered_map<RandomListNode*,RandomListNode*> mmap;
       RandomListNode* nhead = new RandomListNode(head->label);
       mmap[head] = nhead;
       RandomListNode* ntail = nhead, *p = head->next;
       while(p){
           RandomListNode* temp = new RandomListNode(p->label);
           mmap[p] = temp;
           ntail->next = temp;
           ntail = ntail->next;
           p = p->next;
       }
       p = head;
       while(p){
          mmap[p]->random = mmap[p->random];
          p = p->next;
       }
       return nhead;
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！