复杂单向链表的复制

发布时间:2020-07-15 03:00:58 作者:栗先生
来源:网络 阅读:557

    一个单向的复杂链表,每个节点有两个指针,一个是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;
}

推荐阅读:
  1. 剑指offer:复杂链表的复制
  2. 复杂链表的复制(一道算法题)

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

复杂节点

上一篇:【沫沫金】安卓手机版 - 日期控件

下一篇:Parrot 国内源

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》