【初阶数据结构】单链表经典OJ题

目录标题

原题展现
题目解析
代码展现
- 1.创建新节点
- 2.拷贝random指针
- 3.将新节点尾插

原题展现

该题是力扣上的第138题，题目链接如下：随机链表的复制。
在这里插入图片描述

题目解析

我们发现这个链表和一般的链表存在着一点点区别，那就是每个节点多了一个random指针，它指向的是随机的节点。题目要求我们构造原链表的深拷贝，简单的说就是构造一个新的链表，要求这两个链表是要一摸一样，包括里面的值和指针。
我们发现，如果链表中不存在random指针时，该链表的拷贝是非常简单的，但是这个链表中存在了random这个指针，且random指向随机，那么我们在拷贝时也不太好拷贝。此时我们就要想一个办法让我们在拷贝时能让新节点快速找到random指向的节点。
此时我们可以将拷贝节点插入在原节点的后面，这样使得拷贝节点和原节点建立了一个关联关系。
在这里插入图片描述
我们将新节点插入完之后，开始将random指针进行拷贝，我们发现，原链表的蓝1这个节点的random指向蓝2这个节点，此时我们同样要让绿1这个节点指向绿2这个节点，我们可以找到拷贝节点和原节点之间存在的一个关系：新节点->random = 原节点->random->next。也就是新节点的random要指向的节点是原节点的random节点的下一个节点。
在这里插入图片描述
此时，我们就可以通过循环，将每个新节点加入random指针，使其指向正确的新的节点，最后将这些新拷贝好的节点一个个尾插就能组成一个新的链表。

代码展现

我们要理清思路，才能更好地写代码，根据该题，我们就能分几个步骤：

创建新节点插入到每个节点的后面
根据原节点的random拷贝到新节点中
将新节点拿下来尾插成为新链表

1.创建新节点

    Node* pcur = head;while(pcur){Node* copy = (Node*)malloc(sizeof(Node));copy->val = pcur->val;copy->next = pcur->next;pcur->next = copy;pcur = copy->next;}

使用malloc创建新节点，并将原节点的值同样赋给新节点
并且将新节点插入到原节点后面

2.拷贝random指针

    pcur = head;while(pcur){Node* copy = pcur->next;if(pcur->random != NULL){copy->random = pcur->random->next;}else{copy->random = NULL;}pcur = pcur->next->next;}

让pcur重新指向头结点循环
先要判断pcur->random是否为空
新节点的random要指向的节点是原节点的random节点的下一个节点

3.将新节点尾插

    pcur = head;Node* copyhead = NULL, *copytail = NULL;while(pcur){Node* next = pcur->next->next;if(copytail == NULL){copyhead = copytail = pcur->next;}else{copytail->next = pcur->next;copytail = copytail->next;}pcur = next;}

建立新的链表，将新节点尾插到新链表中
尾插后可以将原链表复原，只需在pcur = next前加一句pcur->next = next;（不复原也可以）

至此，这道题目结束，下面是完整代码：

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* pcur = head;while(pcur){Node* copy = (Node*)malloc(sizeof(Node));copy->val = pcur->val;copy->next = pcur->next;pcur->next = copy;pcur = copy->next;}pcur = head;while(pcur){Node* copy = pcur->next;if(pcur->random != NULL){copy->random = pcur->random->next;}else{copy->random = NULL;}pcur = pcur->next->next;}pcur = head;Node* copyhead = NULL, *copytail = NULL;while(pcur){Node* next = pcur->next->next;if(copytail == NULL){copyhead = copytail = pcur->next;}else{copytail->next = pcur->next;copytail = copytail->next;}pcur = next;}return copyhead;
}