Copy List with Random Pointer

138. 随机链表的复制

分析

在原链表中插入新节点
- 遍历原链表，对于每个节点 p，创建一个新节点 q
- 将新节点插入到原节点 p 和 p->next 之间，形成交错链表结构：原节点 -> 新节点 -> 原节点
复制 random 指针
- 再次遍历交错链表，对于每个原节点 p，将 p->next->random 设置为 p->random->next，即新节点的 random 指向对应的新节点
拆分链表
- 遍历交错链表，将新节点从中分离出来，形成深拷贝链表，同时还原原链表的结构

时间复杂

遍历链表三次，分别处理插入节点、复制 random 指针、拆分链表，时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution
{
public:
    Node* copyRandomList(Node* head)
    {
        // 第 1 步：在原链表中插入新节点
        for (Node* p = head; p; p = p->next->next)
        {
            Node* q = new Node(p->val); // 创建新节点
            q->next = p->next;         // 插入新节点到原节点之后
            p->next = q;
        }

        // 第 2 步：复制 random 指针
        for (Node* p = head; p; p = p->next->next)
        {
            if (p->random)
                p->next->random = p->random->next; // 设置新节点的 random
        }

        // 第 3 步：拆分链表
        Node* dummy = new Node(-1); // 虚拟头节点
        Node* cur = dummy;
        for (Node* p = head; p; p = p->next)
        {
            Node* q = p->next;       // 取出新节点
            cur = cur->next = q;     // 将新节点连接到深拷贝链表
            p->next = q->next;       // 恢复原链表结构
        }

        return dummy->next;
    }
};