LeetCode 复制带随机指针的链表

亦凉 2023-06-04 14:52 27阅读 0赞

题目链接：[https://leetcode-cn.com/problems/copy-list-with-random-pointer/][https_leetcode-cn.com_problems_copy-list-with-random-pointer]

### 题目大意 ###

略。

### 分析 ###

空间复杂度 O(1) 的做法非常开拓思维。

### 代码如下 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 // Definition for a Node.
     3 class Node {
     4 public:
     5     int val;
     6     Node* next;
     7     Node* random;
     8 
     9     Node() {}
    10 
    11     Node(int _val, Node* _next, Node* _random) {
    12         val = _val;
    13         next = _next;
    14         random = _random;
    15     }
    16 };
    17 */
    18 class Solution {
    19 public:
    20     Node* copyRandomList(Node* head) {
    21         if(head == NULL) return NULL;
    22         
    23         Node *p1 = head, *p2, *newhead;
    24         
    25         // 在原链表中交替嵌入新节点
    26         while(p1 != NULL) {
    27             Node *t = new Node();
    28             
    29             t->next = p1->next;
    30             t->val = p1->val;
    31             p1->next = t;
    32             p1 = t->next;
    33         }
    34         
    35         newhead = head->next;
    36         p1 = head;
    37         p2 = newhead;
    38         // 拷贝random
    39         while(1) {
    40             if(p1->random == NULL) p2->random = NULL;
    41             else p2->random = p1->random->next;
    42             p1 = p2->next;
    43             if(p1 == NULL) break;
    44             p2 = p1->next;
    45         }
    46         
    47         p1 = head;
    48         p2 = newhead;
    49         // 分离
    50         while(1) {
    51             p1 = p1->next = p2->next;
    52             if(p1 == NULL) break;
    53             p2 = p2->next = p1->next;
    54         }
    55         return newhead;
    56     }
    57 };

转载于:https://www.cnblogs.com/zaq19970105/p/11348716.html

[https_leetcode-cn.com_problems_copy-list-with-random-pointer]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/c7699fdc23614443b85b552b08163293.png