请教狗狗题：复制带随机指针的链表 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教狗狗题：复制带随机指针的链表

请教狗狗题：复制带随机指针的链表# JobHunting - 待字闺中

h*72013-08-22 07:08

1 楼

中文OJ上有的：
给定一个单链表，链表除了包含next指针外，还包含一个random指针，该指针指向链表
中某个结点。
请复制链表到一个新的链表，random指针需要指向新链表中对应的结点。比如原链表某
个结点random指针指向第2个结点，那么新结点的random指针也要指向到新链表的第2个
结点。
要求是不用extra space，就是除了被复制的链表外，不允许用哈希之类的映射表了吧
，没想出怎么搞，请大牛指点，thanks !!

r*e2013-08-22 07:08

2 楼

搜复杂链表复制，何海涛的blog里有这题。

【在 h*****7 的大作中提到】

: 中文OJ上有的：
: 给定一个单链表，链表除了包含next指针外，还包含一个random指针，该指针指向链表
: 中某个结点。
: 请复制链表到一个新的链表，random指针需要指向新链表中对应的结点。比如原链表某
: 个结点random指针指向第2个结点，那么新结点的random指针也要指向到新链表的第2个
: 结点。
: 要求是不用extra space，就是除了被复制的链表外，不允许用哈希之类的映射表了吧
: ，没想出怎么搞，请大牛指点，thanks !!

t*32013-08-22 07:08

3 楼

原链表节点数据结构是
class node{
int value;
node next;
node random;
}
假设原链表是：
a-b-c
然后复制每个节点到自己的后面（不许额外存储空间，O(n)时间）：
a-a'-b-b'-c-c'
然后对于每个新复制的带'号节点复制random指针。以a'为例：
a'.random = a.random.next;

【在 h*****7 的大作中提到】