#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
class Node {
public:
Node* next;
Node* rand;
int value;
};
Node* copy_list_with_rand_ptr(Node* list) {
if(list == NULL) {
return NULL;
}
/*
* 参考:http://hi.baidu.com/gkqofoydngbjqtq/item/6345d6104b7a8d06e65c36a3
* 1、复制链表中的每一个节点放到自己的next
* 2、修改偶数位置的节点的rand为rand-->next
* 3、将链表分离,奇数节点组成原链表,偶数为复制的结果
* */
//第一步
Node* p = list;
while( p ) {
//复制节点
Node* n = new Node();//内存不足没有考虑
n->rand = p->rand;
n->value = p->value;
//插入链表
n->next = p->next;
p->next = n;
p = n->next;
}
//第二步,修改rand指针
p = list;
while( p ) {
p = p->next;
p->rand = p->rand->next;
p = p->next;
}
//第三步
p = list;
Node* result = list->next;
Node* t = result;
while( p ) {
p->next = t->next;
p = p->next;
if( p ) {
t->next = p->next;
t = t->next;
} else {
t->next = NULL;
}
}
return result;
}
void print_list(Node* list) {
printf("\n");
if( list == NULL) {
return;
}
while( list ) {
printf("next=%x, rand=%x, value=%d\n", int(list->next), int(list->rand), list->value);
list = list->next;
}
printf("\n");
}
int main()
{
const int N = 10;
Node ns[N];
for(int i = 0; i < N; i++) {
if(i < N-1) {
ns[i].next = &ns[i+1];
} else {
ns[i].next = NULL;
}
ns[i].rand = &ns[rand() % N];
ns[i].value = i;
}
print_list(ns);
Node* copied = copy_list_with_rand_ptr(ns);
print_list(copied);
return 0;
}
分享到:
相关推荐
1.14 我似乎不能成功定义一个链表。我试过typedefstruct{char*item;NODEPTRnext;}*NODEPTR;但是编译器报了错误信息。难道在C语言中结构不能包含指向自己的指针吗? 1.15 如何定义一对相互引用的结构? 1.16 ...
o 2.6 我似乎不能成功定义一个链表。我试过 typedef struct { char *item; NODEPTR next; } *NODEPTR; 但是编译器报了错误信息。难道在C语言中一个结构不能包含指向自己的指针吗? o 2.7 怎样建立和理解非常复杂的...
范例1-46 仅设表尾指针循环链表的合并 110 ∷相关函数:MergeList_CL函数 1.3.16 正序输出双向链表 113 范例1-47 正序输出双向链表 113 ∷相关函数:ListInsert函数 ListTraverse函数 1.3.17 逆向输出双向链表 ...
1.14 我似乎不能成功定义一个链表。我试过typedef struct{char *item; NODEPTR next;}* NODEPTR; 但是编译器报了错误信息。难道在C语言中结构不能包含指向自己的指针吗? 7 1.15 如何定义一对相互引用的结构?...
范例1-46 仅设表尾指针循环链表的合并 110 ∷相关函数:MergeList_CL函数 1.3.16 正序输出双向链表 113 范例1-47 正序输出双向链表 113 ∷相关函数:ListInsert函数 ListTraverse函数 1.3.17 逆向输出双向链表 ...
范例1-46 仅设表尾指针循环链表的合并 110 ∷相关函数:MergeList_CL函数 1.3.16 正序输出双向链表 113 范例1-47 正序输出双向链表 113 ∷相关函数:ListInsert函数 ListTraverse函数 1.3.17 逆向输出双向链表 ...
(4) 复制粘贴位图到“掩码”位图的设备描述表中,这个时候“掩码”位图设备描述表中存放的位图与位图设备描述表中的位图一样; (5) 把需要透明绘制的位图与对话框绘图相应区域的背景进行逻辑异或操作绘制到...
1.6 我似乎不能成功定义一个链表。我试过typedef struct f char *item; NODEPTR next; g *NODEPTR; 但是编译器报了错误信 息。难道在C语言中一个结构不能包含指向自己的指针吗? . . . . 3 1.7 怎样建立和理解非常...