list_deepcopy.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
  int val;
  struct node *next;
  struct node *random;
} node;

node *create_list(int n) {
  node **nodes = malloc(n * sizeof(node *));

  for (int i = 0; i < n; i++) {
    nodes[i] = malloc(sizeof(node));
    nodes[i]->val = rand();
    nodes[i]->next = NULL;
    nodes[i]->random = NULL;
  }

  for (int i = 0; i < n; i++) {
    if (i != n - 1) {
      nodes[i]->next = nodes[i + 1];
    }
    if (rand() % n != 0) {
      nodes[i]->random = nodes[rand() % n];
    }
  }

  node *head = nodes[0];
  free(nodes);

  return head;
}

int list_len(node *list) {
  int len = 0;
  while (list) {
    len++;
    list = list->next;
  }
  return len;
}

node *copy_list(node *list) {
  node *n = list;
  node *prev = NULL;
  node *copy = NULL;
  
  int len = list_len(list);
  node **map = malloc(2 * sizeof(node *) * len);

  for (int i = 0; i < len; i++, n = n->next) {
    node *next = malloc(sizeof(node));
    next->val = n->val;
    next->next = NULL;
    next->random = n->random;
    if (prev) {
      prev->next = next;
    } else {
      copy = next;
    }
    map[i * 2] = n;
    map[i * 2 + 1] = next;
    prev = next;
  }

  n = copy;
  while (n) {
    if (n->random) {
      for (int i = 0; i < len; i++) {
        if (map[i * 2] == n->random) {
          n->random = map[i * 2 + 1];
          break;
        }
      }
    }
    n = n->next;
  }

  free(map);

  return copy;
}

void print_list(char *label, node *list) {
  printf("%s\n", label);
  while (list) {
    if (list->random) {
      printf("%d -> %d\n", list->val, list->random->val);
    } else {
      printf("%d\n", list->val);
    }
    list = list->next;
  }
}

void free_list(node *list) {
  while (list) {
    node *next = list->next;
    free(list);
    list = next;
  }
}

int main(int argc, char **argv) {
  srand(time(NULL));

  node *head = create_list(10);
  print_list("Original", head);

  node *copy = copy_list(head);
  free_list(head);
  print_list("Copy", copy);
  free_list(copy);

  return 0;
}