看不懂这题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

看不懂这题

看不懂这题# JobHunting - 待字闺中

k*r2013-01-13 08:01

1 楼

http://www.mitbbs.com/article_t/Piebridge/32576601.html
完美情人啊

c*a2013-01-13 08:01

2 楼

是不是shuffle打乱链表啊
copy a linked list where the data member of each node in the linked list
could be any other node in the linked list.

w*s2013-01-13 08:01

3 楼

perfect if you qualify.

【在 k****r 的大作中提到】

: http://www.mitbbs.com/article_t/Piebridge/32576601.html
: 完美情人啊

l*a2013-01-13 08:01

4 楼

linked list有一个指针data member,可能指向这个连表中任意结点

【在 c*****a 的大作中提到】

: 是不是shuffle打乱链表啊
: copy a linked list where the data member of each node in the linked list
: could be any other node in the linked list.

v*n2013-01-13 08:01

5 楼

pp is not clear

j*y2013-01-13 08:01

6 楼

struct Node
{
Node * next;
Node * node;
}
copy this linked list

【在 c*****a 的大作中提到】

: 是不是shuffle打乱链表啊
: copy a linked list where the data member of each node in the linked list
: could be any other node in the linked list.

l*n2013-01-13 08:01

7 楼

这个是小兰，还是新蛋

【在 k****r 的大作中提到】

: http://www.mitbbs.com/article_t/Piebridge/32576601.html
: 完美情人啊

M*52013-01-13 08:01

8 楼

写了个c++版本的，O(n)的time efficiency和O(n)的space efficiency，不知道有没有
更优化的？比如no extra space and only one time walk-through?
struct Node{
Node* data;
Node* next;
};
Node* copyLinkedList(Node* head){
if(!head)
return NULL;

std::map node_map;
Node* new_head = copyLinkedListHelper(head, node_map);

Node* cur = new_head;
while(head){
cur->node = node_map[head->node];
cur = cur->next;
head = head->next;
}
return new_head;
}
Node* copyLinkedListHelper(Node* head, std::map& n_map){
if(!head)
return NULL;

Node* n = new Node;
n_map[head] = n;
n->next = copyLinkedListHelper(head->next, n_map);

return n;
}

k*r2013-01-13 08:01

9 楼

幸好ld不去鹊桥,这样的mm就是他想要的梦中情人啊,靠

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

: 这个是小兰，还是新蛋

c*a2013-01-13 08:01

10 楼

写出来了
public static ListNode copyLink(ListNode node){
ListNode original = node, head = null, newOne=null,next;
//insert node inbetween, so abc becomes aabbcc
while(original!=null){
newOne = new ListNode(original.val);
next = original.next;
original.next = newOne;
newOne.next =next;
original = next;
}
//new list
head = node.next;
//copying random link
original = node;
while(original!=null){
original.next.datamember = original.datamember.next;
original = original.next.next;
}
//separte two lists out
original = node;
newOne = original.next;
while(original!=null && newOne!=null){
next = newOne.next;
if(next!=null){
original.next= next;
newOne.next = next.next;
newOne = newOne.next;
}
original = next;
}
return head;
}

k*82013-01-13 08:01

11 楼

不知道为什么要贴这种看不清楚脸的照片去征婚

M*52013-01-13 08:01

12 楼

这个idea很好，duplicate linked list，估计我要是在phone interview的时候这么写
肯定会出bug，但是这在space上应该是很优化的

【在 c*****a 的大作中提到】

: 写出来了
: public static ListNode copyLink(ListNode node){
: ListNode original = node, head = null, newOne=null,next;
: //insert node inbetween, so abc becomes aabbcc
: while(original!=null){
: newOne = new ListNode(original.val);
: next = original.next;
: original.next = newOne;
: newOne.next =next;
: original = next;