[133] Clone Graph

好抽象的題目 Orz 感覺應該有hard 啊 T_T

這好像才是linked list 的極致展現  XD

就這個無向圖 graph 其實是在node 間指來指去

今天要deep copy的時候，可以用一個visited 去記錄，或是一開始宣告一個pointer array 代表待會兒會一一指去每一個node，當這個pointer 還沒有被指向任何人時，表市它還沒有被allocate 空間，因此我們先對它做malloc 。如果它已經有指去node了，那就可以直接return 了。

可以在紙上把graph 畫一畫，感受一下pointer 滿天飛的混亂 囧

這題沒看別人寫法我還真不會寫Orz

/**

* Definition for a Node.

* struct Node {

* int val;

* int numNeighbors;

* struct Node** neighbors;

* };

*/

struct Node* deepCopy(struct Node* s, struct Node** ret) {

if (ret[s->val] != NULL)

return ret[s->val];

struct Node *newNode = malloc (sizeof (struct Node));

newNode->val = s->val;

newNode->numNeighbors = s->numNeighbors;

newNode->neighbors = malloc (sizeof (struct Node*)* (s->numNeighbors));

ret[newNode->val]=newNode;

for (int i=0; i < newNode->numNeighbors; ++i)

newNode->neighbors[i] = deepCopy(s->neighbors[i],ret);

return newNode;

}

struct Node *cloneGraph(struct Node *s) {

if (s==NULL)

return NULL;

struct Node **ret= calloc (101, sizeof(struct Node *));

return deepCopy(s,ret);

}