方法图解:
class Solution {
public:Node* copyRandomList(Node* head) {if ( !head ) {return nullptr;}Node *cur = head;// 1. 在原节点的每个节点后创建一个节点while ( cur ) {Node *newNode = new Node(cur -> val);newNode -> next = cur -> next;cur -> next = newNode;cur = cur -> next ->next;}// 2. 更新新节点的random指针cur = head;while ( cur ) {if ( cur -> random == nullptr ) {cur -> next -> random = nullptr;} else {cur -> next -> random = cur -> random -> next;}cur = cur -> next -> next;}// 3. 将两个链表拆开Node *dummy = new Node(-1);Node *curnew = dummy, *curold = head;while ( curold ) {curnew -> next = curold -> next;curnew = curnew -> next;curold->next = curnew->next;curold = curold -> next;}return dummy -> next;}
};