h*****7
发帖数: 103 | 1 中文OJ上有的：
给定一个单链表，链表除了包含next指针外，还包含一个random指针，该指针指向链表
中某个结点。
请复制链表到一个新的链表，random指针需要指向新链表中对应的结点。比如原链表某
个结点random指针指向第2个结点，那么新结点的random指针也要指向到新链表的第2个
结点。
要求是不用extra space，就是除了被复制的链表外，不允许用哈希之类的映射表了吧
，没想出怎么搞，请大牛指点，thanks !! |
r*****e
发帖数: 792 | 2 搜复杂链表复制，何海涛的blog里有这题。
【在 h*****7 的大作中提到】
: 中文OJ上有的：
: 给定一个单链表，链表除了包含next指针外，还包含一个random指针，该指针指向链表
: 中某个结点。
: 请复制链表到一个新的链表，random指针需要指向新链表中对应的结点。比如原链表某
: 个结点random指针指向第2个结点，那么新结点的random指针也要指向到新链表的第2个
: 结点。
: 要求是不用extra space，就是除了被复制的链表外，不允许用哈希之类的映射表了吧
: ，没想出怎么搞，请大牛指点，thanks !!
|
t*********3
发帖数: 87 | 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 的大作中提到】
: 中文OJ上有的：
: 给定一个单链表，链表除了包含next指针外，还包含一个random指针，该指针指向链表
: 中某个结点。
: 请复制链表到一个新的链表，random指针需要指向新链表中对应的结点。比如原链表某
: 个结点random指针指向第2个结点，那么新结点的random指针也要指向到新链表的第2个
: 结点。
: 要求是不用extra space，就是除了被复制的链表外，不允许用哈希之类的映射表了吧
: ，没想出怎么搞，请大牛指点，thanks !!
|
s*******n
发帖数: 305 | 4 大牛果然厉害， mark了
LZ， 弱弱的问下， 中文OJ在哪里？ |
u*****o
发帖数: 1224 | 5 http://112.124.16.117/
【在 s*******n 的大作中提到】
: 大牛果然厉害， mark了
: LZ， 弱弱的问下， 中文OJ在哪里？
|
u*****o
发帖数: 1224 | 6 这方法也太巧妙了吧。真是聪明人啊。
【在 t*********3 的大作中提到】
: 原链表节点数据结构是
: class node{
: int value;
: node next;
: node random;
: }
: 假设原链表是：
: a-b-c
: 然后复制每个节点到自己的后面（不许额外存储空间，O(n)时间）：
: a-a'-b-b'-c-c'
|
s*******n
发帖数: 305 | 7
多谢
【在 u*****o 的大作中提到】
: http://112.124.16.117/
|
l****i
发帖数: 2772 | |
g****r
发帖数: 1589 | 9 这个给力啊，是版上的人做的吗，不过怎么不弄个域名啊？
【在 u*****o 的大作中提到】
: http://112.124.16.117/
|
a*****u
发帖数: 1712 | 10 狗狗出过
我面rocketfuel也被问过
【在 l****i 的大作中提到】
: 这题我在版上看到几次，好像都说是软软题。。。
|
f****e
发帖数: 34 | 11 域名正在备案中, 天朝特色 :)
【在 g****r 的大作中提到】
: 这个给力啊，是版上的人做的吗，不过怎么不弄个域名啊？
|
