剑指offer编程题—复杂链表的复制

---

历时8天的鹅厂暑期实习面试告一段落，终于又可以安静刷题了（等结果出来了再更一波面经）。

---

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

题解思路1

1. 遍历链表，复制每一个节点，新的节点链接在原节点的后面。假设原链表为：A->B->C ，复制节点后变成A->A'->B->B'->C->C'；
2. 重新遍历链表，根绝旧链表的random指针初始化新节点的random指针。curNode->next->random=curNode->random->next;
3. 拆分链表，得到原链表和复制的新链表。

图片来源网友

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead==NULL) return NULL;
        RandomListNode* curNode=pHead;
        while(curNode){
            RandomListNode* tmp=new RandomListNode(curNode->label);
            tmp->next=curNode->next;
            curNode->next=tmp;
            curNode=tmp->next;
        }
        curNode=pHead;
        while(curNode){
            if(curNode->random){
                curNode->next->random=curNode->random->next;
            }
            curNode=curNode->next->next;
        }
        RandomListNode* pCloneHead=pHead->next;
        curNode=pHead;
        RandomListNode* tmp;
        while(curNode->next){
            tmp=curNode->next;
            curNode->next=tmp->next;
            curNode=tmp;
        }
        return pCloneHead;
    }
};

上面的解题思路时常规做法，但是没有考虑链表中是否存在环，如果链表中存在环，上述做法就容易陷入死循环。
思路2

1. 第一次遍历原链表，用map建立原链表中节点与新链表中相应节点的一一映射关系，并初始化next关联。此时map中key对应的时原链表中的节点，value对应的是新链表中的节点，mp.find(curNode)==mp.end()判断条件用于判断链表中是否存在环；
2. 再次遍历原链表，初始化复制链表的random关联，也就是 mp[curNode]->random=mp[curNode->random];

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead==NULL) return NULL;
        map<RandomListNode*,RandomListNode*> mp;
        mp.clear();
        RandomListNode* pCloneHead=new RandomListNode(pHead->label);
        mp[pHead]=pCloneHead;
        RandomListNode* curNode=pHead->next;
        RandomListNode* cloneNode=pCloneHead;
        while(curNode && mp.find(curNode)==mp.end()){
            RandomListNode* tmp=new RandomListNode(curNode->label);
            cloneNode->next=tmp;
            cloneNode=tmp;
            mp[curNode]=tmp;
            curNode=curNode->next;
        }
        curNode=pHead;
        int i=0; //记录访问节点的数量，避免在环中陷入死循环
        while(curNode && i<mp.size()){
            if(curNode->random){
                mp[curNode]->random=mp[curNode->random];
            }
            curNode=curNode->next;
            ++i;
        }
        return mp[pHead];
    }
};

解题思路3
思路2虽然考虑了链表中的环，但是题目中讲到random指针指向任意一个节点，并没有讲这个任意节点是否包含在链表中，如果这个任意节点不在链表中，那么只用next指针并不能遍历到所有节点。思路3来源与mark大佬。
下面的做法是用图的思路来做的，刚开始看到这种做法的时候，感觉dfs1中的dfs1(curNode->random)和dfs2中的dfs2(curNode->random)都可以省略，其实不然，正因为考虑到random指向的节点不一定在链表中，只用next指针不一定能遍历完所有节点，所以才这么做的。
总的思路还是先用map建立新节点与旧节点的映射关系，然后按照旧链表给新节点的指针赋值（也就是建立边的映射关系）。set在这里只是用来标记节点是否被访问过，其实也可以参考思路2中的做法，用计数的方法来判断链表节点是否都访问过，避免在链表的环中循环。

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
private:
    map<RandomListNode*,RandomListNode*> mp;
    set<RandomListNode*> visit;
public:
    void dfs1(RandomListNode* curNode){
        if(curNode && mp.find(curNode)==mp.end()){
            RandomListNode *node=new RandomListNode(curNode->label);
            mp[curNode]=node;
            dfs1(curNode->next);
            dfs1(curNode->random);
        }
    }
    void dfs2(RandomListNode* curNode){
        if(curNode && visit.find(curNode)==visit.end()){
            if(curNode->next) mp[curNode]->next=mp[curNode->next];
            if(curNode->random) mp[curNode]->random=mp[curNode->random];
            visit.insert(curNode);
            dfs2(curNode->next);
            dfs2(curNode->random);
        }
    }
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead==NULL) return NULL;
        mp.clear();
        dfs1(pHead);
        dfs2(pHead);
        return mp[pHead];
    }
};