雅灭蝶!! - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

雅灭蝶!!

雅灭蝶!!# Joke - 肚皮舞运动

A*g2013-07-26 07:07

1 楼

过不了，请大牛看看，我在本地测试过好像没问题啊
----------------------------------------------
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {

if (head==null) return null;
RandomListNode p = head;
while (p != null) {
RandomListNode newNode = new RandomListNode(p.label);
newNode.next = p.next;
p.next = newNode;
p = newNode.next;
}

p = head;
RandomListNode p2 = head.next;
RandomListNode newHead = p2;

while (p2.next != null) {
if (p.random==null) {
p2.random = null;
} else {
p2.random = p.random.next;
}
p.next = p2.next;
p = p.next;
p2.next = p.next;
p2 = p2.next;
}
p.next = null;

return newHead;
}
}
--------------------------------------------------
Submission Result: Wrong Answer
Input: {-1,-1}
Output: {-1,#}
Expected: {-1,-1}
不明白这个{-1,#}什么意思，但是本机测试可以通过-1,-1啊...
谢谢！

x*o2013-07-26 07:07

2 楼

d*n2013-07-26 07:07

3 楼

You need to have 3 while loops, the second one fix the random pointer and
the third one separate old list and new list.

【在 A******g 的大作中提到】

: 过不了，请大牛看看，我在本地测试过好像没问题啊
: ----------------------------------------------
: public class Solution {
: public RandomListNode copyRandomList(RandomListNode head) {
:
: if (head==null) return null;
: RandomListNode p = head;
: while (p != null) {
: RandomListNode newNode = new RandomListNode(p.label);
: newNode.next = p.next;

t*t2013-07-26 07:07

4 楼

小心10万伏特。

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

: h

a*e2013-07-26 07:07

5 楼

{-1,-1} 是链表只有一个节点的情况。
你的code在这种情况下直接跳过第二个循环了。新链表的随机指针是NULL

S*02013-07-26 07:07

6 楼

同求问题，本地是过的，runtime error, 上代码。
public class Solution {
public static RandomListNode copyRandomList(RandomListNode head) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(head == null) return null;
RandomListNode pointer, res_pointer;
pointer = head;
while(pointer != null){
RandomListNode temp = new RandomListNode(pointer.label);
temp.random = null;
temp.next = pointer.next;
RandomListNode next = pointer.next;
pointer.next = temp;
pointer = next;
}
RandomListNode res = head.next;

pointer = head;
while(pointer != null){
pointer.next.random = pointer.random.next;
pointer = pointer.next.next;
}
pointer = head;
res_pointer = head.next;
while(pointer != null && res_pointer != null){
pointer.next = pointer.next.next;
if(res_pointer.next != null) res_pointer.next = res_pointer.next
.next;
pointer = pointer.next;
res_pointer = res_pointer.next;
}
return res;
}
}

J*32013-07-26 07:07

7 楼

第二个while loop 判断 pointer.random

f*42013-07-26 07:07

8 楼

第二个loop就是改random pointer的，不能把链断开。因为后面的random pointer有可
能会指向前面的node，或者它本身，这样，你把前面的指针断开了，就找不到复制的那
个node了。。。所以第二个loop就改random pointer，再多加一个loop专门改链的指针

热点事件追踪