题目描述

现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。请对这个链表进行深拷贝。

(构造法) $O(n)$

• Part1，构造新链表。复制原链表中节点i（复制label值），得到克隆节点i’，并将得到克隆节点i’插入源节点i后面，即 1 -> 1’ -> 2 -> 2’ -> NULL。
• Part2，复制random指向关系。遍历part1中的链表，复制节点i的随机指针指向关系给克隆节点i’。即将节点i的random -> next 赋值给 克隆节点i’的random；
• Part3，分离链表。恢复原链表，并且返回新链表的头节点。

时间复杂度

遍历三次链表，所以时间复杂度是$O(n)$

额外空间复杂度 O(1)

参考文献

[1].https://www.youtube.com/watch?v=OvpKeraoxW0&gl=SG
[2].https://www.acwing.com/solution/LeetCode/content/5512/

C++ 代码

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution{
public:
    RandomListNode *copyRandomList(RandomListNode *head)
    {
        if(!head) return NULL;
        RandomListNode *cur = head;
        // RandomListNode *dummy = new RandomListNode(head -> label);          
        // -1- 每个节点后插入一个自身的克隆节点
        while(cur)
        {
            RandomListNode *mirror = new RandomListNode(cur -> label);
            mirror -> next = cur -> next; 
            cur -> next = mirror;
            cur = mirror -> next;
        }

        // -2- 对最后一个克隆节点外的克隆节点进行随机指针域复制
        cur = head;        
        while(cur)
        {
            // 克隆原链表节点中的随机指针域的指向关系
            if(cur -> random)    // 复制random是非空的节点的random， 也就是说要当心空指针；
                cur -> next -> random = cur -> random -> next;
            cur = cur -> next -> next;
        }
        // -3- 分离两个链表
        RandomListNode *new_head = head -> next; 
        cur = head;     
        while(cur)
        {
            RandomListNode *mirror = cur -> next;
            cur -> next = cur -> next -> next;
            cur = cur -> next;
            if(cur) mirror -> next = cur -> next;
        }
        return new_head;
    }
};