问一个链表的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个链表的问题

问一个链表的问题# JobHunting - 待字闺中

b*n2010-11-06 07:11

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*t2010-11-06 07:11

2 楼

新链表是unique的节点还是duplicated节点组成的？

d*e2010-11-06 07:11

3 楼

这里有
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid=31563337

【在 b****n 的大作中提到】

: 如果一个链表是用如下的数据
: struct Node
: {
: int data;
: Node* next;
: Node* another;
: };
: 实现
: Node* duplicateList(Node* list)
: //

c*22010-11-06 07:11

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*n2010-11-06 07:11

5 楼

这帖子里讨论出了2种方法，我再加一种：
因为每个Node里的data是int，size跟一个pointer一样，所以首先把原链表的所有data
读出来，
按顺序存到一个array里。然后复制链表，同时把原链表的每个node里的data用作指针
，指向复制出
的新链表中的对应节点。这样原链表和新链表的每个节点都有了单向对应关系，用这个
关系可以把新链
表中的another指针解决。最后，把array里的data按顺序写到原链表中。
方法跟帖子里的“梯子法“类似，区别在于使用了更少的额外空间。

【在 d**e 的大作中提到】

: 这里有
: http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid=31563337

j*x2010-11-06 07:11

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*x2010-11-06 07:11

7 楼

第二次遍历的时候通过原节点next指针得到下一个复制节点；但是不能破坏
next指针，因为某些原节点的next值需要用来恢复复制节点的another；只
能在第三次遍历时恢复next

表中的对应
里）；
节点的下一
5' ...；
已通过next恢复原

【在 j********x 的大作中提到】

: 如下：
: 第一次遍历原链表，复制节点，并将复制节点的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恢复原