当前位置: 首页 > 文档资料 > LeetCode 题解 >

Linked List - Copy List with Random Pointer

优质
小牛编辑
135浏览
2023-12-01

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指针的链表random可能指向空,也可能指向链表中的任意一个节点。

对于通常的链表,我们递归依次拷贝就可以了,同时用一个hash表记录新旧节点的映射关系用以处理random问题。

代码如下:

  1. class Solution {
  2. public:
  3. RandomListNode *copyRandomList(RandomListNode *head) {
  4. if(head == NULL) {
  5. return NULL;
  6. }
  7. RandomListNode dummy(0);
  8. RandomListNode* n = &dummy;
  9. RandomListNode* h = head;
  10. map<RandomListNode*, RandomListNode*> m;
  11. while(h) {
  12. RandomListNode* node = new RandomListNode(h->label);
  13. n->next = node;
  14. n = node;
  15. node->random = h->random;
  16. m[h] = node;
  17. h = h->next;
  18. }
  19. h = dummy.next;
  20. while(h) {
  21. if(h->random != NULL) {
  22. h->random = m[h->random];
  23. }
  24. h = h->next;
  25. }
  26. return dummy.next;
  27. }
  28. };

但这题其实还有更巧妙的作法。假设有如下链表:

  1. |------------|
  2. | v
  3. 1 --> 2 --> 3 --> 4

节点1的random指向了3。首先我们可以通过next遍历链表,依次拷贝节点,并将其添加到原节点后面,如下:

  1. |--------------------------|
  2. | v
  3. 1 --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
  4. | ^
  5. |-------------------|

因为我们只是简单的复制了random指针,所以新的节点的random指向的仍然是老的节点,譬如上面的1和1’都是指向的3。

调整新的节点的random指针,对于上面例子来说,我们需要将1’的random指向3’,其实也就是原先random指针的next节点。

  1. |--------------------------|
  2. | v
  3. 1 --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
  4. | ^
  5. |-------------------------|

最后,拆分链表,就可以得到深拷贝的链表了。

代码如下:

  1. class Solution {
  2. public:
  3. RandomListNode *copyRandomList(RandomListNode *head) {
  4. if(head == NULL) {
  5. return NULL;
  6. }
  7. //遍历并插入新的节点
  8. RandomListNode* n = NULL;
  9. RandomListNode* h = head;
  10. while(h) {
  11. RandomListNode* node = new RandomListNode(h->label);
  12. node->random = h->random;
  13. n = h->next;
  14. h->next = node;
  15. node->next = n;
  16. h = n;
  17. }
  18. //调整random
  19. h = head->next;
  20. while(h) {
  21. if(h->random != NULL) {
  22. h->random = h->random->next;
  23. }
  24. if(!h->next) {
  25. break;
  26. }
  27. h = h->next->next;
  28. }
  29. //断开链表
  30. h = head;
  31. RandomListNode dummy(0);
  32. RandomListNode* p = &dummy;
  33. while(h) {
  34. n = h->next;
  35. p->next = n;
  36. p = n;
  37. RandomListNode* nn = n->next;
  38. h->next = n->next;
  39. h = n->next;
  40. }
  41. return dummy.next;
  42. }
  43. };