|
| 1 | +/** |
| 2 | + * Definition for a Node. |
| 3 | + * struct Node { |
| 4 | + * int val; |
| 5 | + * struct Node *next; |
| 6 | + * struct Node *random; |
| 7 | + * }; |
| 8 | + */ |
| 9 | + |
| 10 | +/* |
| 11 | + Time: O(n) |
| 12 | + Space: O(1) |
| 13 | +*/ |
| 14 | + |
| 15 | +typedefstructNodeNode; |
| 16 | +structNode*copyRandomList(structNode*head) { |
| 17 | + |
| 18 | +if(head==NULL) |
| 19 | + { |
| 20 | +returnNULL; |
| 21 | + } |
| 22 | + |
| 23 | +/** |
| 24 | + * Insert each new node after each original node |
| 25 | + */ |
| 26 | +Node*curr=head; |
| 27 | +while(curr) |
| 28 | + { |
| 29 | +// Create the new node |
| 30 | +Node*newNode= (Node*)malloc(sizeof(Node)); |
| 31 | +newNode->val=curr->val; |
| 32 | + |
| 33 | +// Insert new node after the original node |
| 34 | +newNode->next=curr->next; |
| 35 | +curr->next=newNode; |
| 36 | + |
| 37 | +// Move curr to the next original node |
| 38 | +curr=curr->next->next; |
| 39 | + } |
| 40 | + |
| 41 | + |
| 42 | +/** |
| 43 | + * Add the random node for each new node |
| 44 | + */ |
| 45 | +curr=head; |
| 46 | +Node*newNode=NULL; |
| 47 | +while(curr) |
| 48 | + { |
| 49 | +// The new node is the next node to the original node |
| 50 | +newNode=curr->next; |
| 51 | + |
| 52 | +if(curr->random) |
| 53 | + { |
| 54 | +newNode->random=curr->random->next; |
| 55 | + } |
| 56 | +else |
| 57 | + { |
| 58 | +newNode->random=NULL; |
| 59 | + } |
| 60 | + |
| 61 | +// Move curr to the next original node |
| 62 | +curr=curr->next->next; |
| 63 | + } |
| 64 | + |
| 65 | +/** |
| 66 | + * Separate the original nodes list from the new nodes list |
| 67 | + */ |
| 68 | +Node*originalList=head; |
| 69 | +Node*copiedList=head->next; |
| 70 | +Node*copiedListHead=head->next; |
| 71 | +while(originalList) |
| 72 | + { |
| 73 | +originalList->next=originalList->next->next; |
| 74 | +if(copiedList->next) |
| 75 | + { |
| 76 | +copiedList->next=copiedList->next->next; |
| 77 | + } |
| 78 | +else |
| 79 | + { |
| 80 | +copiedList->next=NULL; |
| 81 | + } |
| 82 | + |
| 83 | +originalList=originalList->next; |
| 84 | +copiedList=copiedList->next; |
| 85 | + } |
| 86 | + |
| 87 | + |
| 88 | +returncopiedListHead; |
| 89 | +} |