解析

hash表

class Solution {
public:
  Node *copyRandomList(Node *head) {
    if (head == nullptr) {
      return nullptr;
    }
    Node *res = new Node(head->val);
    Node *node1 = head;
    Node *node2 = res;
    unordered_map<Node *, Node *> hashTable;

    while (node1 != nullptr && node1->next != nullptr) {
      hashTable.insert({node1, node2});
      node2->next = new Node(node1->next->val);
      node1 = node1->next;
      node2 = node2->next;
    }
    hashTable.insert({node1, node2});

    node1 = head;
    node2 = res;
    while (node1 != nullptr) {
      if (node1->random != nullptr) {
        node2->random = hashTable[node1->random];
      }
      node1 = node1->next;
      node2 = node2->next;
    }
    return res;
  }
};

利用链表指针，无需额外空间

class Solution {
public:
  Node *copyRandomList(Node *head) {
    if (head == nullptr) {
      return nullptr;
    }
    Node *node = head;
    while (node != nullptr) {
      Node *temp = node->next;
      node->next = new Node(node->val);
      node->next->next = temp;
      node = temp;
    }

    node = head;
    while (node != nullptr) {
      if (node->random != nullptr) {
        node->next->random = node->random->next;
      }
      node = node->next->next;
    }

    node = head;
    Node *res = head->next;
    while (node != nullptr) {
      Node *temp = node->next;
      node->next = node->next->next;
      temp->next = node->next == nullptr ? nullptr : node->next->next;
      node = node->next;
    }
    return res;
  }
};

2025-03-26 该篇文章被 HopoZ 打上标签: leetcode 链表 hashTable 指针归为分类: algo