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;
} |