Definition of complex linked lists:

Structure:

typedef struct d{ int data; struct d *next; Struct d *random; // point to a random node}node;Copy the code

So they want to copy this complicated linked list, and there are usually three ways to do it, and solution number two is to use space for efficiency, using a hash table. Solution 3 is to directly create N’ to be copied after node N of the original linked list. In this case, the random of N’ points to N->random->next, and finally the random pointer of N’ points to the corresponding node. And then you just split the two lists.

#include <stdio.h> #include <stdlib.h> typedef struct d{ int data; struct d *next; struct d *random; }node; Node *creatLink(int *a,int *rand,int len) {node * TMP [len]; int n=0; node *head=(node *)malloc(sizeof(node)); head->data=a[n]; node *ret=head; tmp[n]=head; for(n=1; n<len; n++) { node *s=(node *)malloc(sizeof(node)); s->data=a[n]; s->next=NULL; head->next=s; head=s; tmp[n]=head; } n=0; for(node *t=ret; t; t=t->next) { t->random=tmp[rand[n++]]; } return ret; } node *split(node *h) // Split N+N' list and return N' list {printf("I am here!" ); node *ret=h->next; node *p=h; node *q=h->next; for(; p;) { p->next=q->next; q->next=p->next; p=q->next; if(p! =NULL) { q=p->next; } } return ret; } node *copyLink(node *s) {node *p,*h,*ret; h=ret=s; for(; h;) {// The for loop iterates through the list and copies the node N' of the list to the node N after node N. n->data=h->data; n->next=h->next; h->next=n; h=n->next; } for(h=s,p=s->next; h;) {p->random=h->random->next; h=h->next->next; if(h! =NULL) { p=h->next; } } ret=split(ret); return ret; } void PrintLink(node *s) {printf("\n"); for(; s; s=s->next) { printf("%d->",s->data); }} void PrintRand(node *s) {printf("\n"); for(; s; s=s->next) { printf("%d->",s->random->data); }} int main() {int a[]={0,1,2,3,4}; ,3,1,0,2 int randArray [] = {4}; int len=sizeof(a)/sizeof(a[0]); node *s=creatLink(a,randArray,len); PrintLink(s); PrintRand(s); node *cop=copyLink(s); // PrintLink(cop); PrintRand(cop); }Copy the code