新乡网站建设_页面设计word_推动防控措施持续优化_seo优化工程师

随机链表的复制

问题分析

链表中的每个节点包含三个属性：val（节点的值），next（指向下一个节点的指针），以及random（一个随机指针，可以指向链表中的任意节点，或者为NULL）。我们的目标是创建一个新的链表，其中每个节点的值与原链表中相应节点的值相同，并且新链表中的next和random指针也正确地指向新链表中的节点。

算法分为三个主要步骤：

1. 复制节点并插入到原节点后面：

◦ 遍历原链表，为每个节点创建一个副本，并将副本插入到原节点的后面。
◦ 这一步确保了每个原节点和其副本节点相邻，便于后续设置next和random指针。

2. 复制随机指针：

◦ 再次遍历链表，这次是为了复制每个副本节点的random指针。
◦ 由于副本节点紧跟在原节点之后，原节点的random指针指向的节点的下一个节点就是副本节点的random指针应该指向的节点。

3. 分离原链表和新链表：

◦ 遍历链表，将每个副本节点从原链表中分离出来，形成一个新的链表。
◦ 使用尾插法构建新链表，这样可以避免在构建新链表时破坏原链表的结构。

代码实现

代码实现遵循上述算法设计，具体步骤如下：

1. 初始化指针和变量：

◦ 使用cur指针遍历原链表。
◦ 使用copyHead和copyTail指针来构建和维护新链表。

2. 复制节点：

◦ 为每个节点创建副本，并将其插入到原节点之后。
◦ 更新cur指针以继续遍历。

3. 复制随机指针：

◦ 再次遍历链表，为每个副本节点设置random指针。
◦ 更新cur指针以继续遍历。

4. 分离链表：

◦ 遍历链表，将副本节点从原链表中分离出来，并构建新链表。
◦ 使用尾插法将副本节点添加到新链表中。

5. 返回新链表的头节点：

◦ 返回copyHead，即新链表的头节点

classSolution {
public
:Node* copyRandomList(Node* head) {// 1.拷贝链表，并插入到原节点的后面Node* cur = head;while(cur){Node* next = cur->next;Node* copy = (Node*)malloc(sizeof(Node));copy->val = cur->val;// 插入cur->next = copy;copy->next = next;// 迭代往下走cur = next;}// 2.置拷贝节点的randomcur = head;while(cur){Node* copy = cur->next;if(cur->random != NULL)copy->random = cur->random->next;elsecopy->random = NULL;cur = copy->next;        }// 3.解拷贝节点，链接拷贝节点Node* copyHead = NULL, *copyTail = NULL;cur = head;while(cur){Node* copy = cur->next;Node* next = copy->next;// copy解下来尾插if(copyTail == NULL){copyHead = copyTail = copy;}else{   copyTail->next = copy;copyTail = copy;}cur->next = next;cur = next;}return copyHead;}
};