双向链表和链表的复制

[bosthhe1]

如上图，双向链表的复制，思路是将链表的每个节点拷贝一份，复制的节点连接到下一个节点，然后将原节点链接到复制的节点，依次往复如下图 之后进行依次内部拷贝，链接其中的关系，然后再断开链接，将原链表链接，拷贝链表链接

[bosthhe1]

SListRandom SListCopy(SListRandom Ahead) { assert(Ahead); SListRandom AAhead=Ahead; SListRandom Next= Ahead; while(AAhead!=NULL) { Next = Next ->next; SListRandom Newnode = (SListRandom )malloc(sizeof(SListRandom)); Newnode->val=AAhead->val; Newnode->next =Next; AAhead->next=Newnode; AAhead = Next; } SListRandom cur=Ahead; SListRandom Copy=Ahead; while(AAhead!=NULL) { if(cur -> random == NULL) { Copy->random=NULL; } else {Copy = cur->next;//指向拷贝节点 Copy->random=cur->random->next;//这里先指向random是指向那个节点，再指向next是直线，节点的拷贝节点。 cur=Copy->next; } } //开始断开链表，重新链接 SListRandom cur=Ahead; SListRandom Copy=Ahead->next; SListRandom AAhead=Copy;//保存头节点 SListRandom Next=Copy->next; SListRandom * CopyNext=Next->next; while(cur) { cur->next=Next; Copy->next=CopyNext cur =Next; Copy = CopyNext; Next= CopyNext->next; CopyNext = Next->next; } cur->next = NULL; return AAhead }