首页 > 代码库 > leetcode -- Copy List with Random Pointer

leetcode -- Copy List with Random Pointer

2024-07-17 00:27:35   223人阅读

 你以为那是你的极限，也许只是别人的起点

[问题描述]

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

深度拷贝一个带有随机指针的链表

[解题思路]

 

首先：复制新的节点，插入到对应节点的后面

然后：更新random域，p1->next->random = p1->random->next;

最后：链表拆分出来即可。

 

 1 RandomListNode *Solution::copyRandomList(RandomListNode *head) 2 { 3     if (head == NULL) 4         return head; 5     RandomListNode *p1 = head; 6     RandomListNode *ans = head; 7     while (p1){//复制 8         RandomListNode *tmp = new RandomListNode(p1->label); 9         tmp->next = p1->next;10         p1->next = tmp;11         p1 = p1->next->next;12     }13     p1 = head;14     while (p1){//更新random域15         if (p1->random != NULL){16             p1->next->random = p1->random->next;17         }18         p1 = p1->next->next;19     }20     p1 = head;//链表拆分21     ans = head->next;22     RandomListNode *p2 = ans;23     while (1){24         p1->next = p1->next->next;25         p1 = p1->next;26         if (p2->next == NULL)27             break;28         p2->next = p2->next->next;29         p2 = p2->next;31     }32     return ans;33 }

 


联系
我们