C++速通LeetCode中等第20题-随机链表的复制（三步简单图解）

 方法图解：

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;
    }
};

原文地址：https://blog.csdn.net/weixin_47768406/article/details/142421354

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！