b****n 发帖数: 84 | 1 如果一个链表是用如下的数据
struct Node
{
int data;
Node* next;
Node* another;
};
实现
Node* duplicateList(Node* list)
//
// input: 单链接链表,node->another指向这个链表中的一个任意节点 nodes
within the list
// output: 一个和原来链表有相同结构的新的链表,其中的节点不指向原来的链表
//
能想到的算法是用hash table,O(N), 如果不用额外空间的话, O(N^2)
还有什么更好的办法么? |
d*****t 发帖数: 41 | 2 新链表是unique的节点还是duplicated节点组成的? |
d**e 发帖数: 6098 | 3 这里有
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid=31563337
【在 b****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一个链表是用如下的数据 : struct Node : { : int data; : Node* next; : Node* another; : }; : 实现 : Node* duplicateList(Node* list) : //
|
c***2 发帖数: 838 | 4 very tricky and interesting question.
Here's the BF way:
====================
1) scan original list, save pairs of
data another-data
O(n)
2) copy list using next only and Save pairs of
data node-address
O(n)
3) scan new list and populate another by
look up another-data based on data from 1)
look up node-address based on another-data from 2)
O(n^2)
overall O(n^2)
============================================
any better one? |
g****n 发帖数: 431 | 5 这帖子里讨论出了2种方法,我再加一种:
因为每个Node里的data是int,size跟一个pointer一样,所以首先把原链表的所有data
读出来,
按顺序存到一个array里。然后复制链表,同时把原链表的每个node里的data用作指针
,指向复制出
的新链表中的对应节点。这样原链表和新链表的每个节点都有了单向对应关系,用这个
关系可以把新链
表中的another指针解决。最后,把array里的data按顺序写到原链表中。
方法跟帖子里的“梯子法“类似,区别在于使用了更少的额外空间。
【在 d**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这里有 : http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid=31563337
|
j********x 发帖数: 2330 | 6 如下:
第一次遍历原链表,复制节点,并将复制节点的another指针指向其在原链表中的对应
节点;
将复制链表的节点next指针指向其在原链表中的对应节点的下一个节点;
将原链表节点的next指针指向对应的复制节点;
第二次遍历,对每个复制节点,首先记录其对应的原节点(在another里);
恢复复制节点的another(通过原节点的another-》next);
第三次遍历,因为现在实际上原节点指向复制节点,复制节点的next指向原节点的下一
个节点;如果原节点顺序为:1 2 3 4 5 ... 复制节点为1' 2' 3' 4' 5' ...;
现在实际的顺序为:1 1' 2 2' 3 3' 4 4' 5 5' ...,很容易看出可已通过next恢复原
节点和复制节点的next指针。
常数空间,线性时间 |
j********x 发帖数: 2330 | 7 第二次遍历的时候通过原节点next指针得到下一个复制节点;但是不能破坏
next指针,因为某些原节点的next值需要用来恢复复制节点的another;只
能在第三次遍历时恢复next
表中的对应
里);
节点的下一
5' ...;
已通过next恢复原
【在 j********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如下: : 第一次遍历原链表,复制节点,并将复制节点的another指针指向其在原链表中的对应 : 节点; : 将复制链表的节点next指针指向其在原链表中的对应节点的下一个节点; : 将原链表节点的next指针指向对应的复制节点; : 第二次遍历,对每个复制节点,首先记录其对应的原节点(在another里); : 恢复复制节点的another(通过原节点的another-》next); : 第三次遍历,因为现在实际上原节点指向复制节点,复制节点的next指向原节点的下一 : 个节点;如果原节点顺序为:1 2 3 4 5 ... 复制节点为1' 2' 3' 4' 5' ...; : 现在实际的顺序为:1 1' 2 2' 3 3' 4 4' 5 5' ...,很容易看出可已通过next恢复原
|
l*****o 发帖数: 214 | |
l*****o 发帖数: 214 | |