133. Clone Graph 138. Copy List with Random Pointer 拷贝图和链表

133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

class Solution {

public:

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

        if(node == NULL)

            return NULL;

        UndirectedGraphNode *cloneNode = new UndirectedGraphNode(node->label);

        map<UndirectedGraphNode*, UndirectedGraphNode*> m;

        m[node] = cloneNode;

        queue<UndirectedGraphNode*> q;

        q.push(node);

        while(!q.empty())

        {

            UndirectedGraphNode *t = q.front();

            q.pop();

            for(int i = ; i < t->neighbors.size(); i++)

            {

                UndirectedGraphNode *neighbor = t->neighbors[i];

                if(m.find(neighbor) == m.end())

                {

                    UndirectedGraphNode *p = new UndirectedGraphNode(neighbor->label);

                    m[neighbor] = p;

                    m[t]->neighbors.push_back(p);

                    q.push(neighbor);

                }

                else

                {

                    m[t]->neighbors.push_back(m[neighbor]);

                }

            }

        }

        return cloneNode;

    }

};

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

/**

 * Definition for singly-linked list with a random pointer.

 * struct RandomListNode {

 *     int label;

 *     RandomListNode *next, *random;

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

 * };

 */

（1）

* Consider we have a linked list as below:
*
* node1->random = node2;
* node2->random = node1;
* node3->random = node1;
*
* +-------------+
* | v
* +-------+ +-------+ +-------+
* | node1 |----> node2 |----> node3 |--->NULL
* +-------+ +-------+ +-------+
* ^ ^ | |
* | +-----------+ |
* +--------------------------+
*
*
* To copy the list,
*
* 1) We insert a new node for each node's next position
*
*
* +-------------------------+
* | v
* +--+----+ +-----+ +-------+ +-----+ +-------+ +-----+
* | node1 |---> | NEW |----> node2 |---> | NEW |----> node3 |---> | NEW | ---> NULL
* +-------+ +-----+ +---+---+ +-----+ +--+----+ +-----+
* ^ ^ | |
* | +-----------------------+ |
* +--------------------------------------------------+
*
* 2) Then, we can construt the new node's random pointer:
*
* (node1->next) -> random = (node1->random) -> next;
*
* 3) After we take out all of the "NEW" node to finish the copy.

class Solution {

public:

    RandomListNode *copyRandomList(RandomListNode *head) {

        RandomListNode *p = NULL, *h=NULL, *t=NULL;

        if (head == NULL){

            return NULL;

        }

        //creat a new node for each node and insert its next

        p = head;

        while ( p != NULL){

            RandomListNode *node = new RandomListNode(p->label);

            node->next = p->next;

            p->next = node;

            p = node->next;

        }

        //copy random pointer for each new node

        p = head;

        while (p != NULL){

            if (p->random != NULL){

                p->next->random = p->random->next;

            }

            p = p->next->next;

        }

        //break to two list

        p = head;

        h = t = head->next;

        while ( p != NULL ){

            p->next = p->next->next;

            if (t->next!=NULL){

                t->next = t->next->next;

            }

            p = p->next;

            t = t->next;

        }

        return h;

    }

};

（2）

* Considering we have a link as below:
*
*
* +-------------+
* | v
* +-------+ +-------+ +-------+
* | node1 |----> node2 |----> node3 |--->NULL
* +-------+ +-------+ +-------+
* ^ ^ | |
* | +-----------+ |
* +--------------------------+
*
* 1) Using a map to store each node's random pointer's position
*
* map[node1->random] = 1;
* map[node2->random] = 0;
* map[node3->random] = 0;
*
* 2) Clone the linked list (only consider the next pointer)
*
* new1 --> new2 --> new3 --> NULL
*
* 3) Using an array to strore the order of the cloned linked-list
*
* v[0] = &new1
* v[1] = &new2
* v[2] = &new3
*
* 4) Then we can clone the random pointers.
*
* new->random = v [ map[node->random] ]

class MySolution {

public:

    RandomListNode *copyRandomList(RandomListNode *head) {

        RandomListNode *p = NULL, *h=NULL, *t=NULL;

        //using a map to store the random pointer's postion.

        map<RandomListNode*, int> m;

        //construct the map

        int pos =;

        for ( p = head; p != NULL; p = p->next, pos++){

            m[p] = pos;

        }

        //clone the linked list  (only consider the next pointer)

        //and using a vector to store each node's postion.

        vector<RandomListNode*> v;

        for (p = head; p != NULL; p = p->next){

            RandomListNode *node = new RandomListNode(p->label);

            v.push_back(node);

            if (h==NULL){

                h = t = node;

            }else{

                t->next = node;

                t = node;

            }

        }

        //p => source link head

        //t => new link head

        //move the p and t synchronously, and

        //     t->random = vector[ map[p->random] ];

        for (t=h, p = head; t!=NULL && p!= NULL; p=p->next, t=t->next){

            if (p->random!=NULL) {

                pos = m[p->random];

                t->random = v[pos];

            }

        }

        return h;

    }

};

巴特西

133. Clone Graph 138. Copy List with Random Pointer 拷贝图和链表

最新文章

热门文章