g***j
发帖数: 1275 | 1 经典题目，就是一个linked list，每个节点有一个指针指向random的节点，然后呢，
copy这个list，
基本思路就是在每个节点后面插入一个同样的节点，然后设置好random的指针，最后把
这个list exact出来
举例： 1->2->3->4 其中 1->3 2->4
变成 1->1'->2->2'->3->3'->4->4' 其中 1'->3' 2'->4'
始终有runtime error, 被搞死了，谢了！
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
RandomListNode * p = head;
if(p == NULL) return NULL;
while(p != NULL) {
RandomListNode * newNode = new RandomListNode(p->label);
newNode->next = p->next;
p->next = newNode;
p = p->next->next;
}
p = head;
while(p != NULL) {
if(p->random != NULL)
p->next->random = p->random->next;
p = p->next->next;
}
p = head;
RandomListNode * newHead = p->next;
RandomListNode * q = newHead;
while(p != NULL) {
p->next = q->next;
q->next = p->next->next;
q = q->next;
p = p->next;
}
return newHead;
}
}; |
l*n
发帖数: 529 | 2 思路都有了，竟然不会自己debug，还是不要搞这一行的好。
【在 g***j 的大作中提到】
: 经典题目，就是一个linked list，每个节点有一个指针指向random的节点，然后呢，
: copy这个list，
: 基本思路就是在每个节点后面插入一个同样的节点，然后设置好random的指针，最后把
: 这个list exact出来
: 举例： 1->2->3->4 其中 1->3 2->4
: 变成 1->1'->2->2'->3->3'->4->4' 其中 1'->3' 2'->4'
: 始终有runtime error, 被搞死了，谢了！
: class Solution {
: public:
: RandomListNode *copyRandomList(RandomListNode *head) {
|
g***j
发帖数: 1275 | 3 恩，指教得对！
【在 l*n 的大作中提到】
: 思路都有了，竟然不会自己debug，还是不要搞这一行的好。
|
J****3
发帖数: 427 | |
s*****r
发帖数: 43070 | 5 感觉应该建个cache list, 把已经有的node存里面，这样不会有多余的node
题目的难点是不知道那个是next，哪个是random
【在 g***j 的大作中提到】
: 经典题目，就是一个linked list，每个节点有一个指针指向random的节点，然后呢，
: copy这个list，
: 基本思路就是在每个节点后面插入一个同样的节点，然后设置好random的指针，最后把
: 这个list exact出来
: 举例： 1->2->3->4 其中 1->3 2->4
: 变成 1->1'->2->2'->3->3'->4->4' 其中 1'->3' 2'->4'
: 始终有runtime error, 被搞死了，谢了！
: class Solution {
: public:
: RandomListNode *copyRandomList(RandomListNode *head) {
|
r*******n
发帖数: 3020 | 6 下面while 条件是不是需要加p->next != NULL
while(p != NULL) {
if(p->random != NULL)
p->next->random = p->random->next;
p = p->next->next;
}
【在 g***j 的大作中提到】
: 经典题目，就是一个linked list，每个节点有一个指针指向random的节点，然后呢，
: copy这个list，
: 基本思路就是在每个节点后面插入一个同样的节点，然后设置好random的指针，最后把
: 这个list exact出来
: 举例： 1->2->3->4 其中 1->3 2->4
: 变成 1->1'->2->2'->3->3'->4->4' 其中 1'->3' 2'->4'
: 始终有runtime error, 被搞死了，谢了！
: class Solution {
: public:
: RandomListNode *copyRandomList(RandomListNode *head) {
|
c*****o
发帖数: 1702 | |
t**********h
发帖数: 2273 | 8 帅哥，你好勤奋
【在 g***j 的大作中提到】
: 经典题目，就是一个linked list，每个节点有一个指针指向random的节点，然后呢，
: copy这个list，
: 基本思路就是在每个节点后面插入一个同样的节点，然后设置好random的指针，最后把
: 这个list exact出来
: 举例： 1->2->3->4 其中 1->3 2->4
: 变成 1->1'->2->2'->3->3'->4->4' 其中 1'->3' 2'->4'
: 始终有runtime error, 被搞死了，谢了！
: class Solution {
: public:
: RandomListNode *copyRandomList(RandomListNode *head) {
|
T******e
发帖数: 157 | 9 最后一个loop拆分的时候有问题，假如剩下最后两个节点n和n^
p = n;
q = n^;
此时p 不等于NULL， loop继续， 会有：
p->next = q->next; // 此时p->next 为NULL值
q->next = p->next->next; // p->next->next 非法 |
g***j
发帖数: 1275 | 10 是的，我后来也发现了，谢谢指教
但是，wo当时改了之后还有问题。
【在 T******e 的大作中提到】
: 最后一个loop拆分的时候有问题，假如剩下最后两个节点n和n^
: p = n;
: q = n^;
: 此时p 不等于NULL， loop继续， 会有：
: p->next = q->next; // 此时p->next 为NULL值
: q->next = p->next->next; // p->next->next 非法
|
m**********g
发帖数: 153 | 11 ugly, but works
while(p != NULL) {
p->next = q->next;
if(p->next == NULL)
break;
q->next = p->next->next;
q = q->next;
p = p->next;
} |
