复杂单向链表的复制-创新互联

一个单向的复杂链表，每个节点有两个指针，一个是next，一个是any指针。next指针指向下一个节点，any指针可以指向任意一个节点包括NULL。

    把这个链表复制一遍，要求任意指针指向复制链表相对应的位置。

    我的思想是先在原来的节点后面都加一个新的节点，后面的节点存原来节点的信息。

    第一步，先在每个旧节点后面创建一个新节点，并把值付给新节点。

    第二步，再重新遍历这个新的链表，让新节点的any指针指向前一个旧节点的any指针指向的下一个节点。

    第三步，把加进去的节点一个一个断开，恢复旧的链表。并连成新的链表，此链表就是复制好的链表。

    #include
#include

typedef struct node
{
   int num;
   struct node* next;
   struct node* any;
}NODE;

NODE* create(NODE* phead,int nu)
{
   NODE* tmp = malloc(sizeof(struct node));
   tmp->num = nu;
   if(phead == NULL)
      return tmp;
   else{
      while(phead->next != NULL)
         phead = phead->next;
      phead->next = tmp;
      return tmp;
   }
}

void show(NODE* head)
{
   while(head){
      printf("%d ",head->num);
      if(head->any != NULL)
         printf("%d ",head->any->num);
      else

            printf("NULL ");

        head = head->next;
      printf("\n");
   }
}

NODE* copy(NODE* phead, NODE* head)
{
   NODE* newhead;
   NODE* tmp;
   NODE* newtail;
   NODE* head1 = head;
   phead = head;
   while(head){
      NODE* tmp = malloc(sizeof(struct node));
      tmp->num = head->num;
      tmp->next = head->next;
      head->next = tmp;
      head = head->next->next;
   }
   while(phead){
      if(phead->any == NULL)
         phead->next->any = NULL;
      else{
         phead->next->any = phead->any->next;
      }
      phead = phead->next->next;
   }
   newhead = head1->next;
   newtail = newhead;
   head1 = head1->next->next;
   while(head1){
      tmp = head1->next;
      head1->next = head1->next->next;
      tmp->next = NULL;
      newtail->next = tmp;
      newtail = tmp;
      head1 = head1->next;
   }
   return newhead;
}

int main()
{
   NODE* head = NULL;
   NODE* phead = NULL;
   NODE* tail = head;
   head = create(head,20);
   head->any = NULL;
   tail = create(head,21);
   tail->any = NULL;
   tail = create(tail,22);
   tail->any = head;
   tail = create(tail,23);
   tail->any = head->next;
   tail = create(tail,24);
   tail->any = head->next->next;
   tail = create(tail,25);
   tail->any = NULL;
   tail = create(tail,26);
   tail->any = head;
   show(head);
   printf("the copy is: \n");
   phead = copy(phead,head);
   show(phead);
   return 0;
}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。