由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - reverse random pointers of a single linked list
相关主题
问到linked list 的题目Populating Next Right Pointers in Each Node II
copy link with random additional pointers请教LEETCODE讲解部分的LCA一道题的变种。。
请教下copy list with random pointerleetcode Copy List with Random Pointer
"简单的"linklist的问题有人同看Populating Next Right Pointers in Each Node II的recursive写法么?
linklist exercisePopulating Next Right Pointers in Each Node II
Tricky Pointer Problems -- Which level are you?Leetcode新题 Copy List with Random Pointer
sorted linked list里insert一个nodeLeetcode Copy List with Random Pointer Runtime Error?
remove a node (and its memory) from a doubly linked list求救! Copy List With Random Pointer总是超时
相关话题的讨论汇总
话题: dllnode话题: null话题: head话题: loopdummy话题: node
进入JobHunting版参与讨论
1 (共1页)
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
相关主题
Tricky Pointer Problems -- Which level are you?Populating Next Right Pointers in Each Node II
sorted linked list里insert一个node请教LEETCODE讲解部分的LCA一道题的变种。。
remove a node (and its memory) from a doubly linked listleetcode Copy List with Random Pointer
进入JobHunting版参与讨论
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)

1 (共1页)
进入JobHunting版参与讨论
相关主题
求救! Copy List With Random Pointer总是超时linklist exercise
各位刷友,leetcode里的题目:Copy List with Random PointerTricky Pointer Problems -- Which level are you?
copy list with random pointer 老出错sorted linked list里insert一个node
How can one determine whether a singly linked list has a cycle?remove a node (and its memory) from a doubly linked list
问到linked list 的题目Populating Next Right Pointers in Each Node II
copy link with random additional pointers请教LEETCODE讲解部分的LCA一道题的变种。。
请教下copy list with random pointerleetcode Copy List with Random Pointer
"简单的"linklist的问题有人同看Populating Next Right Pointers in Each Node II的recursive写法么?
相关话题的讨论汇总
话题: dllnode话题: null话题: head话题: loopdummy话题: node