[科技论文网] http://www.scipapers.com    2007-12-01  

拷贝链表的O(n)算法

如结构：

struct List

{

    struct List* data;

    struct List* next;

};

其中next为下一个节点，data指向链表中的随机一个节点。

实现拷贝函数：

struct List * CopyList(struct List* head)

{

}

要求返回一个新的链表，注意：1、新链表中节点的data指向新链表中对应节点，而
非原链表中对应节点。2、不能用缓存（如数组等），可用临时变量。3、必须为O(n)                                          


#include <stdlib.h>

struct node_t
...{
        node_t * data;
        node_t * next;
};

node_t * copy_list(node_t * list)
...{
        if(list==NULL) return NULL;

           //假设原p链为 p1 p2 p3..............

        for(node_t * p=list; p!=NULL; p=p->next->next)
        ...{

                   //新生成一条q链，暂时混插在p链中

                   // 变成 p1 q1 p2 q2 p3 q3 .....................
                node_t * q=new node_t;
                q->next=p->next;
                p->next=q;
        }

        for(node_t * p=list; p!=NULL; p=p->next->next)
        ...{//设置q链中节点q1.......qn中的data
                p->next->data=p->data->next;
        }

        node_t * head=list->next;
        node_t * p=list;
        node_t * q=list->next;

        while(q->next!=NULL)
        ...{

                    //把p链和q链分离
                p->next=q->next;
                p=p->next;
                q->next=p->next;
                q=q->next;
        }
        p->next=NULL;

        return head;
}                                                       

    来源：

声明：本文由网友推荐或作者提交，版权归原作者所有，刊登此文仅为传播知识，展示研究成果，提高文章引用率。未经原作者授权，禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络，文章作者不祥，请相关的原创作者与我们联系，以便加上您的署名。