拷贝链表的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;
}