JZ35 复杂链表的复制

方法一：

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
/*
时间复杂度 O(n^2) 空间复杂度O(n)
思路：1.先复制链表（只复制next指针，先不管random指针）
     2.再赋值random指针 （1）找到原始链表中的random指向的位置，计算与头指针的偏移量。
                      （2）在新链表中根据偏移量来确定random指针的指向。
*/
class Solution {
public:
    RandomListNode* Clone_ListNode(RandomListNode* pHead)
    {
        RandomListNode* head = new RandomListNode(-1);
        RandomListNode* cur = head;
        while(pHead != nullptr)
        {
            RandomListNode* new_node = new RandomListNode(pHead->label);
            cur->next = new_node;
            pHead = pHead->next;
            cur = cur->next;
        }
        return head->next;
    }
    RandomListNode* Clone_Random(RandomListNode* pHead,RandomListNode* newHead)
    {
        RandomListNode* pstart = pHead;
        RandomListNode* nstart = newHead;
        RandomListNode* pcur = pHead;
        RandomListNode* ncur = newHead;
        int tag = 0;
        while(pcur && ncur)
        {
            while(pcur->random != pHead)
            {
                pHead = pHead->next;
                tag++;
            }
            pHead = pstart;
            while(tag)
            {
                newHead = newHead->next;
                tag--;
            }
            ncur->random = newHead;
            newHead = nstart;
            pcur = pcur->next;
            ncur = ncur->next;
        }
        return nstart;
    }
    RandomListNode* Clone(RandomListNode* pHead) {
        RandomListNode* newHead = Clone_ListNode(pHead);
        RandomListNode* ans = Clone_Random(pHead,newHead);
        return ans;
    }
};

方法二： 《剑指offer》解法

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
/*
时间复杂度 O(1) 空间复杂度O(n)
思路：1.先复制链表（只复制next指针，先不管random指针），但是新复制的节点添加到源节点的后面
     2.再赋值random指针 （1）找到原始链表中的random指向的位置
                       （2）找到新节点的random的位置（源链表中的后面一位）
     3.分割链表。将原链表与新链表分隔开
*/
class Solution {
public:
    RandomListNode* Clone_ListNode(RandomListNode* pHead)   //1
    {
        RandomListNode* start = pHead;
        while(pHead != nullptr)
        {
            RandomListNode* new_node = new RandomListNode(pHead->label);
            new_node->next = pHead->next;
            pHead->next = new_node;
            pHead = new_node->next;
        }
        return start;
    }
    RandomListNode* Clone_Random(RandomListNode* pHead)   //2
    {
        if(pHead == nullptr) return pHead;
        RandomListNode* pstart = pHead;
        
        while(pHead)
        {
            RandomListNode* new_head = pHead->next;
            if(pHead->random)
                new_head->random = pHead->random->next;
            pHead = new_head->next;
        }
        return pstart;
    }
    RandomListNode* SegamentListNode(RandomListNode* pHead)   //3
    {
        if(!pHead) return nullptr;
        RandomListNode* start = pHead->next;
        RandomListNode* new_head = start;
        while(pHead)
        {
            pHead->next = new_head->next;
            pHead = pHead->next;
            if(pHead)    //这个地方注意判断
            {
                new_head->next = pHead->next;
                new_head = new_head->next;
            }
        }
        return start;
    }
    RandomListNode* Clone(RandomListNode* pHead) {
        pHead = Clone_ListNode(pHead);
        pHead = Clone_Random(pHead);
        return SegamentListNode(pHead);
    }
};