题目本身没有什么难度，现场发挥主要还是考察你对链表和节点的理解以及代码操作的熟练度。

/*
   考虑到题目中用了pointer这个关键词，
   用python或Java来解释其实更麻烦，
   就用纯C和注释尝试一下。

   这个题根据题设和图示，怪是怪在对于random_index
   的理解。

   一种理解是random_index本身是个指针，指向一个整型，
   整型的值存的是当前链表的一个序号,范围是[0, n-1],
   n为链表长度。这种理解相对简单，因为random_index说白了
   就是一个指针指向一个整型。复制完的链表长度不变，所以序号
   可以直接拷贝过来，无非就是因为它是个pointer，在c/c++中
   有额外的内存处理。

   另外一种理解就是random_index本身是一个为了更好表达这个题设的参数，
   实际上节点结构存的只是一个整型，一个next指针，一个random_pointer指针。
   这个理解下，需要计算原链表random_pointer指针所指示的节点序号，
   然后给原链表先做shalldow copy，新链表要存序号和每个节点指针地址的映射，最后再通过
   原链表的序号再遍历新链表填上正确的random_pointer指针所指节点内存地址。

   题目难度一般是面试官最后会问你有没有办法不做shallow copy，一遍遍历就拷贝完所有节点。

   此处解法尊重第一种理解。
*/

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

/*
   定义节点结构、类型
*/
typedef struct node {
   int val;
   int * random_index;
   struct node * next;    
} Node;

/*
   复制单个节点用的帮助函数
*/
Node * copy_node(Node * n) {
   // 分配新节点内存
   Node * new_node = (Node *) malloc(sizeof(Node));
   // 复制节点整型val值
   new_node->val = n->val;
   // 如果原节点random_index pointer不为空
   if (n->random_index != NULL) {
       // 分配新整型空间到内存上
       new_node->random_index = (int*)malloc(sizeof(int));
       // 将原节点random_index所指向的整型写入
       // 新节点的random_index所指向的整型
       *(new_node->random_index) = *(n->random_index);
   }
   new_node->next = NULL;
   return new_node;
}

/*
   电面的话，这个函数加上上面那个copy_node(Node * n)
   差不多就是你要写的代码的全部
*/
Node * copy_list(Node * head) {

   // 复制空链表，返回空链表
   if (head == NULL) {
       return NULL;
   }

   // 单节点情况先处理，创建新链表头节点，
   // 存下内存地址得以返回
   Node * current = head;
   Node * new_current = copy_node(head);
   Node * new_head = new_current;

   // 将原链表遍历指针移动一个节点
   current = current->next;

   // 循环遍历原链表直到末尾，复制出新节点并
   // 连至新链表当前遍历节点的尾端
   while (current != NULL) {
       new_current->next = copy_node(current);
       new_current = new_current->next;
       current = current->next;
   }
   // 返回新链表头节点
   return new_head;
}

/*
   测试辅助函数：
       value：制造节点的整型值
       index：制造节点random_index所指的序号的整型值；-1为null
*/
void fill_in_value_index(Node * n, int value, int index) {
   n->val = value;
   if (index != -1) {
       n->random_index = (int*)malloc(sizeof(int));
       *(n->random_index) = index;
   }
}

/*
   测试辅助函数：
       创建一个题设中的固定链表。
*/
Node * construct_test_list_fixed() {
   //    [7, null]->[13, 0]->[11, 4]->[10, 2]->[1, 0]
   Node * head = (Node*) malloc(sizeof(Node));
   Node * current = head;
   fill_in_value_index(current, 7, -1);
   current->next = (Node*) malloc(sizeof(Node));
   current = current->next;
   fill_in_value_index(current, 13, 0);
   current->next = (Node*) malloc(sizeof(Node));
   current = current->next;
   fill_in_value_index(current, 11, 4);
   current->next = (Node*) malloc(sizeof(Node));
   current = current->next;
   fill_in_value_index(current, 10, 2);
   current->next = (Node*) malloc(sizeof(Node));
   current = current->next;
   fill_in_value_index(current, 1, 0);

   return head;

}

/*
   测试辅助函数：
       打印链表（ascii)到终端上。
   示例：
       [7, null]->[13, 0]->[11, 4]->[10, 2]->[1, 0]
*/
void display_list(Node * head) {
   if (head == NULL) {
       printf("null\n");
       return;
   }
   Node * current = head;
   while (current != NULL) {
       if (current->random_index != NULL) {
           printf("[%d, %d]->", current->val, *(current->random_index));
       } else {
           printf("[%d, null]->", current->val);
       }
       current = current->next;
   }

   printf("null\n");
}

int main () {

   printf("Copying NULL list...\n");
   // 空头节点测试
   Node * test_head = NULL;
   display_list(test_head);
   Node * copy_head = copy_list(test_head);
   display_list(test_head);

   printf("\nCopying single-node list...\n");
   // 单头节点测试
   test_head = (Node*)malloc(sizeof(Node));
   test_head->val = 39;
   test_head->random_index = (int*)malloc(sizeof(int));
   *(test_head->random_index) = 0;
   display_list(test_head);
   copy_head = copy_list(test_head);
   display_list(copy_head);

   free(test_head->random_index);
   free(test_head);

   printf("\nCopying test case list....\n");
   // 制造一个测试用的链表
   //序号：0         1        2        3        4
   //    [7, null]->[13, 0]->[11, 4]->[10, 2]->[1, 0]
   test_head = construct_test_list_fixed();
   // 用ASCII编码在终端显示链表
   display_list(test_head);
   // 调用复制函数，得到深复制所得的链表头节点
   copy_head = copy_list(test_head);
   //  用ASCII编码在终端显示深复制完的链表
   display_list(test_head);

   return 0;
}

/*
Output:

Copying NULL list...
null
null

Copying single-node list...
[39, 0]->null
[39, 0]->null

Copying test case list....
[7, 0]->[13, 0]->[11, 4]->[10, 2]->[1, 0]->null
[7, 0]->[13, 0]->[11, 4]->[10, 2]->[1, 0]->null
*/```