面试题35：复杂链表的复制

请实现函数RandomList* Clone(RandomList* pHead)，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针，还有一个指向任意一个节点的random指针。

解题思路

  这个题目可以分两步来完成：

• 遍历节点的next指针，先复制出所有的节点
• 遍历所有节点的random指针，并修改复制链表的random指针

  通常第一步很简单，可以当做简单链表的复制来解决，但主要是第二步，有几种方案，但是需要一个最优的（复杂度最低的）方案。

• 遍历所有原链表节点，如果某节点存在random节点，那需要从头再遍历一次找到这个节点，时间复杂度O(n^2)
• 第一步遍历所有节点，如果某节点存在random节点，则用HashMap保存这个关系，找到random节点的复杂度可为O(1)
• 在第一步复制链表的过程中，将复制链表放在原链表的后面

  第三种方案是最妙的方案，但是需要将所有复制过程分为3步。分别是复制链表、复制随机指针、分割链表

// 定义复杂链表
struct RandomListNode{
    int label;
    RandomListNode* next;
    RandomListNode* random;
    RandomListNode(int label):label(label), next(nullptr), random(nullptr){}
};

// 普通链表的复制（复制后的链表与原链表无任何关系）
ListNode* cloneBase(ListNode* pHead){
    ListNode* pNode = pHead;
    ListNode* pAns = nullptr;
    ListNode* pAsses = nullptr;

    while(pNode != nullptr){
        // 处理头结点
        if(pAns == nullptr){
            pAns = new ListNode(pNode->val);
            pAsses = pAns;
        }
        pNode = pNode->next;
        if(pNode != nullptr){
            ListNode* pClone = new ListNode(pNode->val);
            pAsses->next = pClone;
            pAsses = pAsses->next;
        }
        else
            pAsses->next = nullptr;
    }
    return pAns;
}

// 复杂链表的复制
void CloneNodes(RandomListNode* pHead){
    if(pHead == nullptr)
        return ;

    RandomListNode* pNode = pHead;
    while(pNode != nullptr){
        RandomListNode* pCloned = new RandomListNode(pNode->label);
        pCloned->next = pNode->next;
        pCloned->random = nullptr;

        pNode->next = pCloned;
        pNode = pCloned->next;
    }
}

// 复制链表的第二部分
void ConnectRandomNodes(RandomListNode* pHead){
    RandomListNode* pNode = pHead;
    while(pNode != nullptr){
        RandomListNode* pCloned = pNode->next;
        if(pNode->random != nullptr){
            pCloned->random = pNode->random->next;
        }
        pNode = pCloned->next;
    }
}

RandomListNode* Clone(RandomListNode* pHead){
    CloneNodes(pHead);
    ConnectRandomNodes(pHead);

    RandomListNode* pNode = pHead;
    RandomListNode* pCloneHead = nullptr;
    RandomListNode* pCloneNode = nullptr;

    // 先复制头指针
    if(pNode != nullptr){
        pCloneHead = pNode->next;
        pCloneNode = pCloneHead;
        // 修改pNode的下一个
        pNode->next = pCloneNode->next;
        pNode = pNode->next;
    }
    while(pNode != nullptr){
        pCloneNode->next = pNode->next;
        pCloneNode = pCloneNode->next;
        pNode->next = pCloneNode->next;
        pNode = pNode->next;
    }
    return pCloneHead;
}

文末附上普通链表的复制

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstring>
#include "ListNode.h"
#include "TreeNode.h"
#include "Graph.h"
using namespace std;

#define MAXNUM 100010
#define DRIFT 1001

// 普通链表的复制（复制后的链表与原链表无任何关系）
ListNode* cloneBase(ListNode* pHead){

    ListNode* pNode = pHead;
    ListNode* pAns = nullptr;
    ListNode* pAsses = nullptr;

    while(pNode != nullptr){
        // 处理头结点
        if(pAns == nullptr){
            pAns = new ListNode(pNode->val);
            pAsses = pAns;
        }

        pNode = pNode->next;
        if(pNode != nullptr){
            ListNode* pClone = new ListNode(pNode->val);
            pAsses->next = pClone;
            pAsses = pAsses->next;
        }
        else
            pAsses->next = nullptr;
    }
    return pAns;
}

int main()
{
    ListNode* pNode1 = createListNode(1);
    ListNode* pNode2 = createListNode(2);
    ListNode* pNode3 = createListNode(3);
    ListNode* pNode4 = createListNode(4);
    ListNode* pNode5 = createListNode(5);

    connectListNodes(pNode1, pNode2);
    connectListNodes(pNode2, pNode3);
    connectListNodes(pNode3, pNode4);
    connectListNodes(pNode4, pNode5);
    ListNode* pClone = cloneBase(pNode1);


    removeNode(&pClone, 4);
    PrintListNodes(pClone);
    PrintListNodes(pNode1);
    return 0;
}