讨论/《算法面试题汇总》 - 复制带随机指针的链表/
《算法面试题汇总》 - 复制带随机指针的链表

C++ 中规中矩

创建节点时直接在原节点后面创建,这样可以利用原始链中的关系找到random指针,此处在原节点后面创建新节点,则新节点random指向也就是原节点 random 指针的 next 地址(因为也是在后面创建)。

实现random指针指向后,需要将两端链表分离,可以依次利用前后指针进行相互指向来作为后续节点,注意这里要回复原链表的关系,不然会造成原链表的破坏。

稍微注意下遍历时的终止条件

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)    return nullptr;
        Node* left = head;
        // 插入节点
        while (left) {
            Node* node = new Node(left->val);
            node->next = left->next;
            left->next = node;
            left = left->next->next;
        }
        // 找到random
        left = head;
        Node* right = head->next;
        while (left) {
            if (left->random == nullptr)  // random 指向空
                right->random = nullptr;
            else                          // random 指向某个节点
                right->random = left->random->next;
            left = left->next->next;
            if (right->next) // 防止最后一个节点出现问题
                right = right->next->next;
        }
        // 连起来
        Node* new_head = head->next;
        left = head;
        right = new_head;
        while (left->next->next) {
            left->next = right->next;
            left = right->next;
            right->next = left->next;
            right = left->next;
        }
        // 末尾的一个单独处理
        left->next = nullptr;
        right->next = nullptr;
        return new_head;
    }
};