题目描述

请实现 $copyRandomList$ 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 $next$ 指针指向下一个节点，还有一个 $random$ 指针指向链表中的任意节点或者 $null$。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

• $-10000 <= Node.val <= 10000$
• $Node.random$ 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

注意： 本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

---

算法

(链表,模拟) $O(n)$

不使用额外空间，分三步处理

1. 遍历一遍链表，在每个节点的后面插入一个与当前节点值相同的节点
2. 再遍历一遍，对于原链表中有 $random$ 域的节点进行赋值 p->next->random = p->random->next
3. 最后将复制出来的链表拆分出来，同时恢复原链表的结构

时间复杂度

遍历链表的时间复杂度是 $O(n)$

空间复杂度

$O(1)$

C++ 代码

/*
// 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) {
        // 1. 复制每个节点接到它的后面
        for (auto p = head; p; ) {
            auto np = new Node(p->val);
            auto next = p->next;
            p->next = np;
            np->next = next;
            p = next;
        }

        // 2. 为复制出来的节点的 random 域赋值
        for (auto p = head; p; p = p->next->next)
            if (p->random)
                p->next->random = p->random->next;

        // 3. 将复制出来的链表从原链表中拆出来
        auto dummy = new Node(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next) {
            cur->next = p->next;
            p->next = p->next->next;
            cur = cur->next;
        }

        return dummy->next;
    }
};