138.c

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

structRandomListNode {
intlabel;
structRandomListNode*next;
structRandomListNode*random;
};

/*
 * http://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/
 */

structRandomListNode*copyRandomList(structRandomListNode*head) {
if (head==NULL) returnNULL;

structRandomListNode*new_node=NULL;
structRandomListNode*p=head;

/* original next points to new_node, new_node->next points to original next */
while (p) {
new_node= (structRandomListNode*)malloc(sizeof(structRandomListNode));
new_node->label=p->label;
new_node->next=p->next;
p->next=new_node;
p=new_node->next;
 }

/* link random pointers */
p=head;
structRandomListNode*new_head=head->next;
structRandomListNode*q=NULL;
while (p) {
q=p->next;
if (p->random) {
q->random=p->random->next;
 }
else {
q->random=NULL;
 }
p=q->next;
 }

/* restore original link list */
p=head;
while (p) {
q=p->next;
p->next=q->next;
p=p->next;
if (p) {
q->next=p->next;
 }
else {
q->next=NULL;
 }
 }

returnnew_head;
}

intmain() {

structRandomListNode*head
= (structRandomListNode*)malloc(4*sizeof(structRandomListNode));
structRandomListNode*one=head;
one->label=1;
structRandomListNode*two=head+1;
two->label=2;
structRandomListNode*three=head+2;
three->label=3;
structRandomListNode*four=head+3;
four->label=4;

one->next=two;
two->next=three;
three->next=four;
four->next=NULL;

one->random=three;
two->random=one;
three->random=NULL;
four->random=four;

structRandomListNode*p=head;
printf("N R\n");
while (p) {
printf("%d ", p->label);
if (p->random) {
printf("%d\n", p->random->label);
 }
else {
printf("NIL\n");
 }
p=p->next;
 }

structRandomListNode*new_head=copyRandomList(head);

p=new_head;
printf("Copied:\n");
printf("N R\n");
while (p) {
printf("%d ", p->label);
if (p->random) {
printf("%d\n", p->random->label);
 }
else {
printf("NIL\n");
 }
p=p->next;
 }

return0;
}