造假发论文的教授，无论绿卡公民都该立地遣返 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

造假发论文的教授，无论绿卡公民都该立地遣返 (转载)

造假发论文的教授，无论绿卡公民都该立地遣返 (转载)# Biology - 生物学

s*n2017-03-22 07:03

1 楼

Consider a Linked List with each Node, in addition to having a 'next'
pointer also has a 'random' pointer. The 'random' pointer points to some
random other Node on the linked list. It may also point to NULL. To simplify
things, no two 'random' pointers will point to the same node, but more than
1 Node's random pointer can point to NULL.
Now please reverse all the random pointers using space O(1)

T*s2017-03-22 07:03

2 楼

【以下文字转载自 Military 讨论区】
发信人: TomsnReuters (汤生撸透射), 信区: Military
标题: 造假发论文的教授，无论绿卡公民都该立地遣返
发信站: BBS 未名空间站 (Wed Mar 22 17:51:28 2017, 美东)
让他们危害母国

m*l2017-03-22 07:03

3 楼

经典踢阿
这个都烂大街了,随便google

simplify
than

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

: Consider a Linked List with each Node, in addition to having a 'next'
: pointer also has a 'random' pointer. The 'random' pointer points to some
: random other Node on the linked list. It may also point to NULL. To simplify
: things, no two 'random' pointers will point to the same node, but more than
: 1 Node's random pointer can point to NULL.
: Now please reverse all the random pointers using space O(1)

e*s2017-03-22 07:03

4 楼

明君！

【在 T**********s 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: TomsnReuters (汤生撸透射), 信区: Military
: 标题: 造假发论文的教授，无论绿卡公民都该立地遣返
: 发信站: BBS 未名空间站 (Wed Mar 22 17:51:28 2017, 美东)
: 让他们危害母国

s*n2017-03-22 07:03

5 楼

来说说思路

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

: 经典踢阿
: 这个都烂大街了,随便google
:
: simplify
: than

P*R2017-03-22 07:03

6 楼

韩春雨遣返到哪里去？

【在 T**********s 的大作中提到】

m*l2017-03-22 07:03

7 楼

clone, 奇偶

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

: 来说说思路

s*n2017-03-22 07:03

8 楼

clone什么？只能用O(1) space，不能再clone一个list

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

: clone, 奇偶

m*l2017-03-22 07:03

9 楼

我看错了,不过这个也是经典题

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

: clone什么？只能用O(1) space，不能再clone一个list

s*n2017-03-22 07:03

10 楼

来说说我的思路，reverse list不难，但是这个问题是有环怎么办：比如a -> b -> c
->a，假设一开始从a开始reverse整个环，然后访问link list的next又遇到了b，这时
候就不能再reverse一次了。
思路：先reverse有环的，再reverse没环的
round 1，找出所有环，把环中最后一个指向special "NodeEnd"，所以a -> b -> c ->
a变成 a->b->c->nodeEnd。
round 2，从LL头开始遍历所有Node，假设Node开始的random pointer路径包含nodeEnd
，则重新构成一个逆向的环。
round 3，从LL头开始遍历所有Node，假设Node开始的random pointer路径包含NULL，
则reverse这个list

w*o2017-03-22 07:03

11 楼

需要同时reverse next pointers吗?

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

s*n2017-03-22 07:03

12 楼

不需要，那是可以完全独立的问题

【在 w****o 的大作中提到】

: 需要同时reverse next pointers吗?

y*n2017-03-22 07:03

13 楼

http://www.sureinterview.com/shwqst/785002/703001

l*c2017-03-22 07:03

14 楼

the way in this link is clear. almost the same way. ding~~~

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

: http://www.sureinterview.com/shwqst/785002/703001

H*r2017-03-22 07:03

15 楼

nice post
thats a clone though

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

: http://www.sureinterview.com/shwqst/785002/703001

l*i2017-03-22 07:03

16 楼

This seems a nice idea, but one question, when you process a node, how do
you know if its random pointer has been reversed already, without marking
each node that you have done reverse?

c
->
nodeEnd

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

: 来说说我的思路，reverse list不难，但是这个问题是有环怎么办：比如a -> b -> c
: ->a，假设一开始从a开始reverse整个环，然后访问link list的next又遇到了b，这时
: 候就不能再reverse一次了。
: 思路：先reverse有环的，再reverse没环的
: round 1，找出所有环，把环中最后一个指向special "NodeEnd"，所以a -> b -> c ->
: a变成 a->b->c->nodeEnd。
: round 2，从LL头开始遍历所有Node，假设Node开始的random pointer路径包含nodeEnd
: ，则重新构成一个逆向的环。
: round 3，从LL头开始遍历所有Node，假设Node开始的random pointer路径包含NULL，
: 则reverse这个list

D*g2017-03-22 07:03

17 楼

This is a pretty tricky question, especially for the loop handling. Here is
my java code, tested with looped case and non-looped case.
public static class DLLNode {
DLLNode prev;
DLLNode next;
int value;

public DLLNode(int value) {
this.value = value;
prev = null;
next = null;
}
}
static DLLNode dummy = new DLLNode(-1);
static DLLNode loopDummy = new DLLNode(-2);
static void printLL(final DLLNode head) {
DLLNode current = head;
while (current != null) {
String s = current.value + ":" + (current.prev != null ? "" +
current.prev.value : "null") + "--";
System.out.print(s);
current = current.next;
}
System.out.println();
}
static DLLNode getRandStart(DLLNode head, DLLNode target) {
if (head == null) {
return head;
}
DLLNode parent = target;
while (parent != null) {
boolean found = false;
DLLNode iter = head;
while (iter != null) {
if (iter.prev == parent) {
found = true;
break;
} else {
iter = iter.next;
}
}
if (found) {
parent = iter;
} else {
break;
}
}
return parent;
}
static DLLNode reverseLLRand(DLLNode head) {
if (head == null || head.prev == null) {
return head;
}
DLLNode cur = head;
DLLNode next = cur.prev;
boolean connectLoop = false;
while (next != null) {
if (next == loopDummy) {
// cur used to be the break point of a loop, reconnect
connectLoop = true;
head.prev = loopDummy;
break;
}
DLLNode nextnext = next.prev;
next.prev = cur;
cur = next;
next = nextnext;
}
if (!connectLoop) {
head.prev = dummy;
}
return head;
}
static DLLNode reverseRandPointer(DLLNode head) {
if (head == null || head.next == null) {
return head;
}

DLLNode out = head;
while (out != null) {
// break the loop if it is
// Check if the rand LL that out is on is already reversed by
traverse till the end and check if it's null or dummy
DLLNode tail = out.prev;
DLLNode secondToTail = out;
// Check if the rand LL that out is on is a loop
while (tail != null && tail != dummy && tail != loopDummy) {
if (tail == out) {
// there is a loop, break
secondToTail.prev = loopDummy;
tail = null;
break;
}
secondToTail = tail;
tail = tail.prev;
}
if (tail != dummy && tail != loopDummy) {
// get the start of the random LL which out is part of
DLLNode start = tail == loopDummy ? out : getRandStart(head,
out);
reverseLLRand(start);
}

out = out.next;
}

DLLNode start = head;
while (start != null) {
// update dummy pointer to null
if (start.prev == dummy ) {
start.prev = null;
}

// reconnect loop
if (start.prev == loopDummy ) {
start.prev = getRandStart(head, start);
}

start = start.next;
}

return head;
}

static void testReverseRandPointer() {
DLLNode a = new DLLNode(1);
DLLNode b = new DLLNode(2);
DLLNode c = new DLLNode(3);
DLLNode d = new DLLNode(4);
DLLNode e = new DLLNode(5);

a.next = b;
b.next = c;
c.next = d;
d.next = e;

a.prev = c;
c.prev = e;
b.prev = d;
printLL(a);
a = reverseRandPointer(a);
printLL(a);
a.prev = c;
c.prev = e;
e.prev = a;
b.prev = d;
d.prev = null;
printLL(a);
a = reverseRandPointer(a);
printLL(a);
}

simplify
than

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

P*l2017-03-22 07:03

18 楼

If we know the direction of the link, that is, pointing to a visited
node or a coming node, this problem is trivial.
To know the direction, we can follow the 'next' field of the nodes from
the node pointed by the 'random' pointer. If the current node was found,
it is pointing backward. Otherwise, forward.
You can use the 'random' pointer field to improve the performance.

some
simplify
more
than

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