【LeetCode】【剑指offer】【复杂链表的复制】

剑指 Offer 35. 复杂链表的复制

请实现 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。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

第一步，在原来的链表的相邻的结点之间生成新的拷贝结点 

 

 

 第二部，完成我们随机结点的拷贝，由于我们的随机结点是在原来的链表的每两个结点之间的，所以找到了原链表结点的随机位置之后，其next就是我们的新的链表的随机结点。

 

第三步，将我们的拷贝好的链表从我们原来的链表上剪下来 

 

 

/*
// 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) {
//在每个结点之间创建copy结点来连接我们原来的链表，copy结点就是我们新生成的拷贝的结点
	Node* cur=head;
//创建一个临时结点，用来遍历我们的链表
    while(cur)
    {
//创建一个新的拷贝结点
        Node* copy=(Node*)malloc(sizeof(Node));
//我们拷贝结点的数据是我们临时结点的数据，
        copy->val=cur->val;
//将我们的拷贝结点插入到我们的cur结点和cur->next结点之间的位置。
        copy->next=cur->next;
        cur->next=copy;
//将我们的cur移动到下一个需要拷贝的结点
        cur=copy->next;
 
    }
//此时我们已经完成步骤一，也就是说我们新的拷贝的结点已经交叉地插入到原来的链表的每两个结点之中了。
 
 
 
//将我们的随机指针拷贝到我们新生成的节点中。
//将我们的临时结点调到原链表的头结点，来重新遍历我们的链表
    cur=head;
    while(cur)
    {
//由于我们前一步中，我们已经把拷贝的结点插入到原来的链表的相邻的两个结点之间了，所以我们的copy结点就是我们的cur结点的next结点
        Node* copy=cur->next;
//如果我们的当前拷贝对象结点的random指针为null，那我们拷贝结点的random的指针也为null
        if(cur->random==NULL)
            copy->random=NULL;
//如果不是的话，我们的拷贝结点的random指针所指向的应该是我们的原来的结点的random指针的下一个结点（应为我们上一步已经将我们的拷贝链表额结点依次插入到我们的原来的链表的每两个结点之间，所以我们的random指针的next就是我们拷贝的链表的对应的位置的结点）
        else
            copy->random=cur->random->next;
//将我们的cur指针指向我们的下一个原链表的结点。
        cur=copy->next;
    }
//此时，我们已经完成了第二步，也就是说我们此时已经将我们的链表的random指针的指向完成了
 
 
 
//第三步我们需要将我们拷贝的结点从我们原来的混合的链表中剪下来，生成一条单独的链表
    cur=head;
//创建两个新的指针，分别指向我们的链表头和链表尾
    Node* copyHead=NULL,*copyTail= NULL;
    while(cur)
    {
        Node* copy=cur->next;
//使用next来保存我们的copy之后的那个结点，放置我们在将我们的拷贝链表中的结点从我们的原链表中剪下来之后，找不到后面的结点。
        Node* next=copy->next;
//如果我们当前copytail为空，也就是说我们当前的拷贝链表中没有一个元素，这时，将我们的拷贝链表的头指针和尾指针都指向我们的copy结点。也就是说我们当前的拷贝链表只有一个结点，此时我们的头指针和尾指针都指向这个结点
 
        if(copyTail==NULL)
        {
            copyHead=copyTail=copy;
        }
//如果不是拷贝链表中的第一个结点，我们将我们当前的copy结点尾插到我们的新生成的链表中，然后将我们的尾指针后移
        else
        {
            copyTail->next=copy;
            copyTail=copyTail->next;
        }
//将我们原来的链表恢复
        cur->next=next;
//将我们的遍历指针移动到下一个结点位置。
        cur=next;
        
    }
//将我们新生成的链表返回。
    return copyHead;
    }
};