Copy List with Random Pointer

描述

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.

分析

无

代码

  1. // Copy List with Random Pointer
  2. // 两遍扫描，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     RandomListNode *copyRandomList(RandomListNode *head) {
  6.         for (RandomListNode* cur = head; cur != nullptr; ) {
  7.             RandomListNode* node = new RandomListNode(cur->label);
  8.             node->next = cur->next;
  9.             cur->next = node;
  10.             cur = node->next;
  11.         }
  13.         for (RandomListNode* cur = head; cur != nullptr; ) {
  14.             if (cur->random != NULL)
  15.                 cur->next->random = cur->random->next;
  16.             cur = cur->next->next;
  17.         }
  19.         // 分拆两个单链表
  20.         RandomListNode dummy(-1);
  21.         for (RandomListNode* cur = head, *new_cur = &dummy;
  22.                 cur != nullptr; ) {
  23.             new_cur->next = cur->next;
  24.             new_cur = new_cur->next;
  25.             cur->next = cur->next->next;
  26.             cur = cur->next;
  27.         }
  28.         return dummy.next;
  29.     }
  30. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/linear-list/linked-list/copy-list-with-random-pointer.html