【链表】 LeetCode138. 复制带随机指针的链表

心已赠人 2022-12-02 13:38 62阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]

### 解答 ###

struct RandomListNode { 
      int label;
      RandomListNode* next;
      RandomListNode* random;
    
      RandomListNode(int x)
          : label(x)
          , next(nullptr)
          , random(nullptr) { 
      }
    };
    
    void PrintRandomList(RandomListNode* head) { 
      while (head != nullptr) { 
        std::cout << "label: " << head->label << "; random: ";
        if (head->random == nullptr) { 
          std::cout << "NULL";
        } else { 
          std::cout << head->random->label;
        }
    
        std::cout << std::endl;
    
        head = head->next;
      }
    }

// 法一：用map记录仪复制前后结点的对应关系
    Node* copyRandomList(Node* head) { 
      Node new_node(-1);
    
      Node* old_head = head;
      Node* new_head = &new_node;
    
      std::unordered_map<Node* /*old*/, Node* /*new*/> node_map;
    
      while (old_head != nullptr) { 
    
        auto node = new Node(old_head->val);
        new_head->next = node;
        new_head = new_head->next;
        node_map[old_head] = node;
        old_head = old_head->next;
      }
    
       old_head = head;
       new_head = new_node.next;
    
      while (old_head != nullptr && new_head != nullptr) { 
        if (old_head->random != nullptr) { 
          auto node = node_map[old_head->random];
          new_head->random = node;
        }
    
        old_head = old_head->next;
        new_head = new_head->next;
      }
    
      return new_node.next;
    }

// 法二：记录链表每个结点的序号，和与结点地址的对应关系。
    RandomListNode* CopyRandomList(RandomListNode *head) { 
      RandomListNode* old_list_head = head;
    
      // 地址对应标号.
      std::map<RandomListNode*, int> old_list_map;
    
      std::list<RandomListNode*> new_nodes;
      int n = 0;
      while ( head != nullptr) { 
        old_list_map[head] = n++;
    
        RandomListNode* new_node = new RandomListNode(*head);
        new_nodes.push_back(new_node);
    
        head = head->next;
      }
      old_list_map[nullptr] = n;
    
      // 标号对应地址。
      std::map<int, RandomListNode*> new_list_map;
    
      n = 0;
      RandomListNode empty_head_node(-1);
      RandomListNode* temp_node = &empty_head_node;
      for (RandomListNode* new_node : new_nodes) { 
        new_list_map[n++] = new_node;
    
        temp_node->next = new_node;
        temp_node = temp_node->next;
      }
    
      temp_node->next = nullptr;
      new_list_map[n] = nullptr;
    
      RandomListNode* new_list_head = empty_head_node.next;
      while (old_list_head != nullptr && new_list_head != nullptr) { 
        int n = old_list_map[old_list_head->random];
        new_list_head->random = new_list_map[n];
    
        old_list_head = old_list_head->next;
        new_list_head = new_list_head->next;
      }
    
      return empty_head_node.next;
    }

void TestCase() { 
      RandomListNode node1(1);
      RandomListNode node2(2);
      RandomListNode node3(3);
      RandomListNode node4(4);
      RandomListNode node5(5);
    
      node1.next = &node2;
      node2.next = &node3;
      node3.next = &node4;
      node4.next = &node5;
    
      node1.random = nullptr;
      node2.random = &node1;
      node3.random = &node2;
      node4.random = &node3;
      node5.random = &node4;
    
      PrintRandomList(&node1);
    
      std::cout << "==============================" << std::endl;
    
      RandomListNode* new_head = CopyRandomList(&node1);
      PrintRandomList(new_head);
    
      // Free memory.
      while (new_head != nullptr) { 
        RandomListNode* temp_node = new_head;
        new_head = new_head->next;
    
        delete temp_node;
        temp_node->next = nullptr;
        temp_node->random = nullptr;
      }
    }
    
    int main() { 
      TestCase();
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d1b4efef633b4adaaaf44539307fe1cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/dba9bd883cc0448dacf3f3bb3e7b3202.png