復雜單向鏈表的復制

    一個單向的復雜鏈表，每個節點有兩個指針，一個是next，一個是any指針。next指針指向下一個節點，any指針可以指向任意一個節點包括NULL。

    把這個鏈表復制一遍，要求任意指針指向復制鏈表相對應的位置。

    我的思想是先在原來的節點后面都加一個新的節點，后面的節點存原來節點的信息。

    第一步，先在每個舊節點后面創建一個新節點，并把值付給新節點。

    第二步，再重新遍歷這個新的鏈表，讓新節點的any指針指向前一個舊節點的any指針指向的下一個節點。

    第三步，把加進去的節點一個一個斷開，恢復舊的鏈表。并連成新的鏈表，此鏈表就是復制好的鏈表。

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

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;
}