一、复杂链表 （1）结点 值域+next域+radom随机域 （2）链表图示 二、复杂链表复制 （1）步骤 1）给原来的每个结点创建一个新结点，将其连接在原来结点之后 2）给新创建的结点连接random域 3）分割新结点和原结点 （2）图示 三、代码实现
#include<stdio.h> #include<stdlib.h> typedef struct ComplexNode { int data; struct ComplexNode* next; struct ComplexNode* random; }ComplexNode,*PComplexNode; PComplexNode CreateNode(int x) { PComplexNode Node=(PComplexNode)malloc(sizeof(ComplexNode)); if (NULL==Node) { printf("out of memory!\n"); exit(EXIT_FAILURE); } Node->data=x; Node->next=NULL; Node->random=NULL; return Node; }; void CreatCompLexlists (PComplexNode* PPHead) { PComplexNode ret1=CreateNode(1); PComplexNode ret2=CreateNode(2); PComplexNode ret3=CreateNode(3); PComplexNode ret4=CreateNode(4); ret1->next=ret2; ret2->next=ret3; ret3->next=ret4; ret1->random=ret4; ret2->random=ret3; ret3->random=ret2; ret4->random=ret1; *PPHead=ret1; } void PrintfComplexList(PComplexNode Plist) { while (Plist) { printf("[%d]→%d\n",Plist->data,Plist->random->data); printf("↓\n"); Plist=Plist->next; } } PComplexNode CloneComplexList(PComplexNode PHead) { //1.给原来的每个结点创建一个新结点，将其连接在原来结点之后 PComplexNode cur=PHead; PComplexNode next=NULL; PComplexNode NewNode=NULL; PComplexNode head=NULL; while (cur) { next=cur->next; NewNode=CreateNode(cur->data); cur->next=NewNode; NewNode->next=next; cur=next; } //2.给新创建的结点连接random域 cur=PHead; while (cur) { NewNode=cur->next; if (cur->random)//淘汰随机域指向空的结点 { next=cur->random->next; NewNode->random=next; } cur=NewNode->next; } //3.分割新结点和原结点 cur=PHead; if (cur!=NULL) { head=cur->next; } while (cur->next->next)//防止cur变为空指针继续对其访问 { NewNode=cur->next; cur->next=NewNode->next; cur=NewNode->next; NewNode->next=cur->next; } cur->next=NULL;//不破坏原链表 return head; } void Test() { PComplexNode Plist; PComplexNode ret1=NULL; CreatCompLexlists(&Plist); printf("原链表：\n"); PrintfComplexList(Plist); printf("end!!!\n"); ret1=CloneComplexList(Plist); printf("新链表：\n"); PrintfComplexList(ret1); printf("复制原链表：\n"); PrintfComplexList(Plist); } int main() { Test(); return 0; }链表拆分（分割新结点和原结点）： 注意最后给原链表最后一个结点的next域赋空，不破坏原链表； 四、运行结果
