LeetCode OJ--Copy List with Random Pointer **

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

https://oj.leetcode.com/problems/copy-list-with-random-pointer/

灵活的指针链表应用。

每个节点有两个指针next,random，对本链表做一个深拷贝。就是完全用新内存弄出一个一样的来。

a链表： a b c三个node

b链表： a1 b1 c1三个node

a->next = a1

a1->next = b

这样建立关系,之后再扫一遍，对a1的random赋值，之后再扫一遍，对a1->next赋值。

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

struct RandomListNode {

     int label;

     RandomListNode *next, *random;

     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}

 };

class Solution {

public:

    RandomListNode *copyRandomList(RandomListNode *head) {

        if(head == NULL)

            return NULL;

        for(RandomListNode *pointer = head;pointer!=nullptr;)

        {

            RandomListNode *link2node = new RandomListNode(pointer->label);

            link2node->next = pointer->next;

            pointer->next = link2node;

            pointer = pointer->next->next;

        }

        for(RandomListNode *pointer = head;pointer!=nullptr;)

        {

            if(pointer->random!=NULL)

                pointer->next->random = pointer->random->next;

            pointer = pointer->next->next;

        }

        RandomListNode *head2 = head->next;

        RandomListNode * pointer2 = nullptr;

        for(RandomListNode *pointer = head;pointer!=nullptr;pointer = pointer->next)

        {

            pointer2 = pointer->next->next;

            if(pointer2 != nullptr)

            {

                pointer->next->next = pointer->next->next->next;

                pointer->next = pointer2;

            }

            else

            {

                pointer->next->next = NULL;

                pointer->next = NULL;

            }

        }

        return head2;

    }

};

int main()

{

    RandomListNode *n1 = new RandomListNode();

    RandomListNode *n2 = new RandomListNode();

    RandomListNode *n3 = new RandomListNode();

    RandomListNode *n4 = new RandomListNode();

    n1->next = n2;

    n2->next = n3;

    n3->next = n4;

    n1->random = n2;

    n2->random = n1;

    n4->random = n4;

    class Solution mys;

    mys.copyRandomList(n1);

}