My code in C. use hashtable


  • 1
    X
    typedef struct entry {
        struct RandomListNode *key;
        struct RandomListNode *val;
        struct entry *next;
    } entry;
    
    int len = 256;
    entry **dict;
    void put(struct RandomListNode *key, struct RandomListNode *val) {
        int idx = abs(key->label) % len;
        entry *n = malloc(sizeof(entry));
        n->key = key;
        n->val = val;
        entry *base = dict[idx];
        n->next = base;
        dict[idx] = n;
    }
    
    struct RandomListNode* get(struct RandomListNode *key) {
        if(key == NULL) return NULL;
        int idx = abs(key->label) % len;
        entry *base = dict[idx];
        while(base) {
            if (base->key == key) {
                return base->val;
            }
            base = base->next;
        }
        return NULL;
    }
    
    struct RandomListNode *copyRandomList(struct RandomListNode *head) {
        struct RandomListNode *cur = head;
        struct RandomListNode store = {-1, NULL, NULL};
        struct RandomListNode *prev = &store;
        if (head == NULL) return NULL;
        dict =  (entry **) calloc(len, sizeof(entry *));
        while(cur) {
            struct RandomListNode *n = malloc(sizeof(*n));
            n->label = cur->label;
            n->random = cur->random;
            n->next = NULL;
            put(cur, n);
            prev->next = n;
            prev = n;
            cur = cur->next;
        }
        cur = store.next;
        while(cur) {
            cur->random = get(cur->random) ;
            cur = cur->next;
        }
        return store.next;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.