leetcode138.随机链表的复制

  

随机链表的复制

问题分析

链表中的每个节点包罗三个属性：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，即新链表的头节点

1. class
2. Solution {
3. public
4. :
5.     Node* copyRandomList(Node* head) {
6.         // 1.拷贝链表，并插入到原节点的后面
7.         Node* cur = head;
8.         while(cur)
9.         {
10.             Node* next = cur->next;
12.             Node* copy = (Node*)malloc(sizeof(Node));
13.             copy->val = cur->val;
15.             // 插入
16.             cur->next = copy;
17.             copy->next = next;
19.             // 迭代往下走
20.             cur = next;
21.         }
23.         // 2.置拷贝节点的random
24.         cur = head;
25.         while(cur)
26.         {
27.             Node* copy = cur->next;
28.             if(cur->random != NULL)
29.                 copy->random = cur->random->next;
30.             else
31.                 copy->random = NULL;
33.             cur = copy->next;        }
35.         // 3.解拷贝节点，链接拷贝节点
36.         Node* copyHead = NULL, *copyTail = NULL;
37.                 cur = head;
38.         while(cur)
39.         {
40.             Node* copy = cur->next;
41.             Node* next = copy->next;
43.             // copy解下来尾插
44.             if(copyTail == NULL)
45.             {
46.                 copyHead = copyTail = copy;
47.             }
48.             else
49.             {   
50.                 copyTail->next = copy;
51.                 copyTail = copy;
52.             }
54.             cur->next = next;
56.             cur = next;
57.         }
59.         return copyHead;
60.     }
61. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。