假设有如下一个链表：
1
2
3
4
5
6
struct Node
{
intvalue ;
struct Node *next ;
struct Node *random ;
}
其中，random指向该链表的任意一个节点或者NULL，请编程实现该链表的深拷贝。
1
Node *deepCopy (Node *head)
解析：把新节点插入到相应的旧节点后面：
分两步
1、构建新节点random指针：new1->random = old1->random->next, new2-random = NULL, new3-random = NULL, new4->random = old4->random->next
2、恢复原始链表以及构建新链表：例如old1->next = old1->next->next,new1->next = new1->next->next
该算法时间复杂度O(N)，空间复杂度O(1)
代码：
Node *deepCopy (Node *head){Node* now = head;Node* next = head->next;while( now != NULL ){Node * copy = new Node;copy->value = now->value;copy->next = now->next;now ->next = copy;now= next;next= next->next;}now = head;while( now != NULL ){now->next->random = now->random->next;now = now->next->next;}Node* head2 = head->next;Node* newHead = head->next;while( head2->next != NULL ){head->next = head2->next;head2->next = head2->next->next;head = head->next;head2 = head2->next;}return newHead;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
往往为了自己的不能失败，而处心积虑前怕狼后怕虎，
