//36.摘抄自题解 class Solution { public: //vector.begin,end是一个左开右闭区间[) vector<Node*> arr; void help(Node* root) { if(root==NULL)return; help(root->left); arr.push_back(root); help(root->right); } Node* treeToDoublyList(Node* root) { if(root==NULL)return NULL; help(root); for(int i=0;i<arr.size()-1;i++) { arr[i]->right=arr[i+1]; arr[i+1]->left=arr[i]; } arr[arr.size()-1]->right=arr[0]; arr[0]->left=arr[arr.size()-1]; return arr[0]; } }; /* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { copynextonly(head); copyrandomonly(head); return res(head); } void copynextonly(Node* head){ Node *qnode; qnode=head; while(qnode!=NULL){ Node* nnode=new Node(qnode->val); // Node *pnode; // pnode->val=head->val; // Node *pnode; nnode->next=qnode->next; nnode->random=NULL; qnode->next=nnode; qnode=nnode->next; } // return head; } private: void copyrandomonly(Node* head){ Node* pnode=new Node(0); pnode=head; while(pnode!=NULL){ if(pnode->random!=NULL){ pnode->next->random=pnode->random->next; } pnode=pnode->next->next; } // return head; } Node* res(Node* head){ if(head==NULL){ return NULL; } Node* pnode=head->next; Node* phead=pnode; head->next=pnode->next; while(pnode->next!=NULL){ // pnode=pnode->next; head=head->next; pnode->next=pnode->next->next; pnode=pnode->next; head->next=pnode->next; } return phead; } };
