请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
我们分三步做。
第一步,复制每一个节点,拼接到原链表中节点的后一个位置。例如,如下有ABCDE五个节点,我们复制A为A1拼接到A后,使A指向A1,A1指向B,以此列推。第一步完成后,举个例子,如第二张图,将由上图变为下图
第二步,处理random指针
第三步,抽出新链表,同时也可以把原链表恢复原样
代码class Solution { public: Node* copyRandomList(Node* head) { //第一步 for (auto p = head; p; p = p->next->next) { auto q = new Node(p->val); q->next = p->next; p->next = q; } //第二步 for (auto p = head; p; p = p->next->next) { if (p->random) { p->next->random = p->random->next; } } //第三步 auto dummy = new Node(-1), cur = dummy; for (auto p = head; p; p = p->next) { cur->next = p->next; cur = p->next; p->next = cur->next; } return dummy->next; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)