diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /copy_list_rand_ptr.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'copy_list_rand_ptr.c')
-rw-r--r-- | copy_list_rand_ptr.c | 94 |
1 files changed, 94 insertions, 0 deletions
diff --git a/copy_list_rand_ptr.c b/copy_list_rand_ptr.c new file mode 100644 index 0000000..544ba3d --- /dev/null +++ b/copy_list_rand_ptr.c @@ -0,0 +1,94 @@ +// 138. Copy List with Random Pointer +#include <stdlib.h> + +/* + A linked list of length n is given such that each node contains an additional + random pointer, which could point to any node in the list, or null. + + Construct a deep copy of the list. The deep copy should consist of exactly n + brand new nodes, where each new node has its value set to the value of its + corresponding original node. Both the next and random pointer of the new nodes + should point to new nodes in the copied list such that the pointers in the + original list and copied list represent the same list state. None of the + pointers in the new list should point to nodes in the original list. + + For example, if there are two nodes X and Y in the original list, where + X.random + --> Y, then for the corresponding two nodes x and y in the copied list, + x.random + --> y. + + Return the head of the copied linked list. + + The linked list is represented in the input/output as a list of n nodes. Each + node is represented as a pair of [val, random_index] where: + + val: an integer representing Node.val + random_index: the index of the node (range from 0 to n-1) that the random + pointer points to, or null if it does not point to any node. + + Your code will only be given the head of the original linked list. +*/ + +struct Node { + int val; + struct Node *next; + struct Node *random; +}; + +int find_position(struct Node *head, struct Node *random) { + if (!random) + return -1; + struct Node *tmp = head; + int idx = 0; + while (tmp) { + if (tmp == random) + return idx; + idx++; + tmp = tmp->next; + } + return -1; +} + +struct Node *copy_step(struct Node *head, struct Node *new_table) { + struct Node *new_head = malloc(sizeof(struct Node)); + int cnt = 0; + new_head->val = head->val; + new_head->next = NULL; + struct Node *ptr = new_head, *tmp = head->next; + new_table[cnt] = ptr; + cnt++; + while (tmp) { + struct Node *n = malloc(sizeof(struct Node)); + n->val = tmp->val; + ptr->next = n; + ptr = n; + tmp = tmp->next; + new_table[cnt] = ptr; + cnt++; + } + ptr->next = NULL; + return new_head; +} + +struct Node *copyRandomList(struct Node *head) { + if (!head) + return NULL; + int random_idx[1000], cnt = 0; + struct Node *new_table[1000], *tmp = head; + while (tmp) { + random_idx[cnt] = find_position(head, tmp->random); + tmp = tmp->next; + cnt++; + } + struct Node *new_head = copy_step(head, new_table); + struct Node *new_tmp = new_head; + for (int i = 0; i < cnt; i++) { + if (random_idx[i] == -1) + new_tmp->random = NULL; + else + new_tmp->random = new_table[random_idx[i]]; + new_tmp = new_tmp->next; + } + return new_head; +} |