69,372
社区成员
发帖
与我相关
我的任务
分享面试题求解
链表的拷贝
如结构：
struct List
{
struct List* data;
struct List* next;
};
其中next为下一个节点，data指向链表中的随机一个节点。
实现拷贝函数：
struct List * CopyList(struct List* head)
{
}
要求返回一个新的链表，注意：
1、新链表中节点的data指向新链表中对应节点，而非原链表中对应节点。2、不能用缓存（如数组等），可用临时变量。
3、必须为O(n)
如结构：
struct List
{
struct List* data;
struct List* next;
};
其中next为下一个节点，data指向链表中的随机一个节点。
实现拷贝函数：
struct List * CopyList(struct List* head)
{
}
要求返回一个新的链表，注意：
1、新链表中节点的data指向新链表中对应节点，而非原链表中对应节点。2、不能用缓存（如数组等），可用临时变量。
3、必须为O(n)
...全文
请发表友善的回复…
发表回复
mlwu3 2006-12-27
- 打赏
- 举报
mark
lcd5 2006-11-20
- 打赏
- 举报
yingge(...木脑壳...) 正解，结帖
pluton 2006-11-18
- 打赏
- 举报
struct List * pList = ( struct List *)malloc(sizeof(struct List ));
KennyLiu 2006-11-18
- 打赏
- 举报
struct List * CopyList(struct List* head)
{
struct List * tList ;
struct List * pHead;
tList = head;
int first=1;
while( tList != NULL)
{
struct List * pList = ( struct List *)malloc(sizeof(struct List* ));
pList->data = tList;
pList->next = tList->next;
if(first == 1)
{
pHead = pList;
first =0;
}
tList = tList->next;
}
return pHead;
}
{
struct List * tList ;
struct List * pHead;
tList = head;
int first=1;
while( tList != NULL)
{
struct List * pList = ( struct List *)malloc(sizeof(struct List* ));
pList->data = tList;
pList->next = tList->next;
if(first == 1)
{
pHead = pList;
first =0;
}
tList = tList->next;
}
return pHead;
}
Leaveye 2006-11-18
- 打赏
- 举报
..
明明是 DuplicateList 非说是 copy 。
明明是 DuplicateList 非说是 copy 。
liuchangyan 2006-11-18
- 打赏
- 举报
mark
yingge 2006-11-18
- 打赏
- 举报
不过最后“原链表和新链表分开”必须重新循环，不能和data赋值(第二个循环)放在一起
data可能指向前面的node ，如果前面已经“分开”就不能实现
-------------------------
是了，说得很对，所以说实践是检验真理的唯一标准，一个没有测试过的程序，我总是觉得有问题。。
谢谢fosjos(无聊的菜鸟程序员) 了。
data可能指向前面的node ，如果前面已经“分开”就不能实现
-------------------------
是了，说得很对，所以说实践是检验真理的唯一标准，一个没有测试过的程序，我总是觉得有问题。。
谢谢fosjos(无聊的菜鸟程序员) 了。
fosjos 2006-11-18
- 打赏
- 举报
To: yingge(...木脑壳...)
方法确实不错，
不过最后“原链表和新链表分开”必须重新循环，不能和data赋值(第二个循环)放在一起
data可能指向前面的node ，如果前面已经“分开”就不能实现
方法确实不错，
不过最后“原链表和新链表分开”必须重新循环，不能和data赋值(第二个循环)放在一起
data可能指向前面的node ，如果前面已经“分开”就不能实现
boxer_tony 2006-11-18
- 打赏
- 举报
mark
yingge 2006-11-18
- 打赏
- 举报
哦， tmp->next=tmp->next->next;这句应该改为
if(tmp->next)
tmp->next=tmp->next->next;
否则会出错
if(tmp->next)
tmp->next=tmp->next->next;
否则会出错
yingge 2006-11-18
- 打赏
- 举报
有点变态的面试题嘛，我没有测试过，不过基本思想就是下面这样了，看注释
struct List * CopyList (struct List * head){
struct List *newhead=NULL,*newnode,*p=head,*tmp;
while(p){
newnode=(struct List *)malloc(sizeof(struct List)); /* 新结点 */
newnode->data=NULL; /* 先不管data指针 */
newnode->next=p->next; /* 这两句将新结点插入到原链表原结点之后 */
p->next=newnode; /* 这两句将新结点插入到原链表原结点之后 */
if(!newhead)
newhead=newnode; /* 设置返回值 */
p=p->next;
}
p=head;
while(p){
tmp=p->next; /* tmp为新结点 */
tmp->data=p->data->next; /* 新结点的data指针指向原结点data指针之后 */
p->next=tmp->next; /* 这两句将原链表和新链表分开，形成两个链表 */
tmp->next=tmp->next->next; /* 这两句将原链表和新链表分开，形成两个链表 */
p=p->next;
}
return newhead; /* 返回新链表的头 */
}
struct List * CopyList (struct List * head){
struct List *newhead=NULL,*newnode,*p=head,*tmp;
while(p){
newnode=(struct List *)malloc(sizeof(struct List)); /* 新结点 */
newnode->data=NULL; /* 先不管data指针 */
newnode->next=p->next; /* 这两句将新结点插入到原链表原结点之后 */
p->next=newnode; /* 这两句将新结点插入到原链表原结点之后 */
if(!newhead)
newhead=newnode; /* 设置返回值 */
p=p->next;
}
p=head;
while(p){
tmp=p->next; /* tmp为新结点 */
tmp->data=p->data->next; /* 新结点的data指针指向原结点data指针之后 */
p->next=tmp->next; /* 这两句将原链表和新链表分开，形成两个链表 */
tmp->next=tmp->next->next; /* 这两句将原链表和新链表分开，形成两个链表 */
p=p->next;
}
return newhead; /* 返回新链表的头 */
}
doudouHuY 2006-11-18
- 打赏
- 举报
感觉不用数组之类的缓冲o(n)实现比较困难，帮顶
heartbeast 2006-11-18
- 打赏
- 举报
由data的随机性，必须查找，怎么可能在O(n)内完成！！！
a_b_c_abc8 2006-11-18
- 打赏
- 举报
觉得只能先按一般链表复制后，再查找比较先的每个节点的data，再在新的链表中查找赋值，觉得很复杂哦。
