leetcode刷题日记——随机链表的复制

[ 题目描述 ]：

[ 思路 ]：

• 题目要钱创建一个新的和给出链表相同的链表，val 和 next 的复制比较简单，关键在于 random 的复制
• 先复制一个 random 不变的新链表，然后通过他在旧链表中的位置，去锁定新链表中 next 需要指向的位置
• 运行如下
  

struct Node* copyRandomList(struct Node* head) {if (!head) return NULL;struct Node* old_nodes[1000];struct Node* new_nodes[1000];int count = 0;struct Node* cur = head;struct Node* copy_head = NULL;struct Node* prev = NULL;while (cur) {struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));new_node->val = cur->val;new_node->next = NULL;new_node->random = cur->random;if (prev)prev->next = new_node;elsecopy_head = new_node;old_nodes[count] = cur;new_nodes[count] = new_node;count++;prev = new_node;cur = cur->next;}for (int i = 0; i < count; i++) {if (new_nodes[i]->random) {for (int j = 0; j < count; j++) {if (old_nodes[j] == new_nodes[i]->random) {new_nodes[i]->random = new_nodes[j];break;}}} else {new_nodes[i]->random = NULL;}}return copy_head;
}

[ 官方题解 ]：

• 方法一：回溯 + 哈希表，用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当拷贝完成，回溯到当前层时，即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，需要首先检查当前节点是否被拷贝过，如果已经拷贝过，可以直接从哈希表中取出拷贝后的节点的指针并返回即可

struct HashTable {struct Node *key, *val;UT_hash_handle hh;
} * cachedNode;struct Node* deepCopy(struct Node* head) {if (head == NULL) {return NULL;}struct HashTable* tmp;HASH_FIND_PTR(cachedNode, &head, tmp);if (tmp == NULL) {struct Node* headNew = malloc(sizeof(struct Node));headNew->val = head->val;tmp = malloc(sizeof(struct HashTable));tmp->key = head, tmp->val = headNew;HASH_ADD_PTR(cachedNode, key, tmp);headNew->next = deepCopy(head->next);headNew->random = deepCopy(head->random);}return tmp->val;
}struct Node* copyRandomList(struct Node* head) {cachedNode = NULL;return deepCopy(head);
}