个人技术分享

一、题目链接：. - 力扣（LeetCode）

二、思路：

1、对原链表遍历，我们在每个结点后面申请一个与之一模一的结点，将其插入到每原来的两个结点之间。（如上图）

2、遍历原链表，进行对随机指针指向的复制

3、最后把那些复制申请的结点剪切下来，形成与原链表相同的链表。

三、代码解释

1.结构体的成员：

struct Node {
     int val;
   struct Node *next;
     struct Node *random;
 };

2.申请结点的函数

struct Node*Buynode(int val)
{
    struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
      newnode->val=val;
      newnode->next=NULL;
      newnode->random=NULL;
      return newnode;
}

参数val为每个结点中的数值。申请新的结点的数值是与原来的相同。

将新结点的数值赋值为val,next  和  random 指针先置为NULL

3.随机链表复制函数

struct Node*Buynode(int val)
{
    struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
      newnode->val=val;
      newnode->next=NULL;
      newnode->random=NULL;
      return newnode;
}

struct Node* copyRandomList(struct Node* head) {
	struct Node*cur1=head;
    //1.从原链表头部遍历，将每个新的结点插入到中间
    while(cur1)
    {
    struct Node*newnode=Buynode(cur1->val);
    newnode->next=cur1->next;
    cur1->next=newnode;
cur1=newnode->next;
    }

    //2.重新遍历，确定好随机指针
    cur1=head;
    while(cur1)
    {
        if(cur1->random!=NULL)//如果原结点的random指针不是NULL
      cur1->next->random=cur1->random->next;//所以，新申请的结点random指针要指向原链表的random指针所指向的结点的下一个结点，也就是那个结点的复制结点
cur1=cur1->next->next;
    }
    
    cur1=head;
    struct Node*nhead=Buynode(-1),*ncur;//创建哨兵位
    ncur=nhead;
  while(cur1)//尾插每一个新申请的结点，从而组成一个新的链表
  {
     ncur->next=cur1->next;
     ncur=cur1->next;

    cur1=cur1->next->next;
  }
        return nhead->next;//返回哨兵位的下一个结点作为开头
}

如果原结点的random指针不是NULL，所以，新申请的结点random指针要指向原链表的random指针所指向的结点的下一个结点，也就是那个结点的复制结点，这样就与原链表保持一致，而且新链表中的结点与原链表的结点没有指向关系。