s******n 发帖数: 3946 | 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) |
m*******l 发帖数: 12782 | 2 经典踢阿
这个都烂大街了,随便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)
|
s******n 发帖数: 3946 | 3 来说说思路
【在 m*******l 的大作中提到】 : 经典踢阿 : 这个都烂大街了,随便google : : simplify : than
|
m*******l 发帖数: 12782 | 4 clone, 奇偶
【在 s******n 的大作中提到】 : 来说说思路
|
s******n 发帖数: 3946 | 5 clone什么?只能用O(1) space,不能再clone一个list
【在 m*******l 的大作中提到】 : clone, 奇偶
|
m*******l 发帖数: 12782 | 6 我看错了,不过这个也是经典题
【在 s******n 的大作中提到】 : clone什么?只能用O(1) space,不能再clone一个list
|
s******n 发帖数: 3946 | 7 来说说我的思路,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****o 发帖数: 2260 | 8 需要同时reverse next pointers吗?
【在 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)
|
s******n 发帖数: 3946 | 9 不需要,那是可以完全独立的问题
【在 w****o 的大作中提到】 : 需要同时reverse next pointers吗?
|
y*****n 发帖数: 243 | |
|
|
l****c 发帖数: 782 | 11 the way in this link is clear. almost the same way. ding~~~
【在 y*****n 的大作中提到】 : http://www.sureinterview.com/shwqst/785002/703001
|
H****r 发帖数: 2801 | 12 nice post
thats a clone though
【在 y*****n 的大作中提到】 : http://www.sureinterview.com/shwqst/785002/703001
|
l***i 发帖数: 1309 | 13 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********g 发帖数: 650 | 14 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 的大作中提到】 : 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)
|
P********l 发帖数: 452 | 15 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 的大作中提到】 : 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)
|