链表含有随机rand指针的复制
#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;}