Problem:

复制含有随机指针节点的链表

【题目】 一种特殊的链表节点类描述如下：

public class Node {

public int value;

public Node next;

public Node rand;

public Node(int data) { this.value = data; }

}

Node类中的value是节点值，next指针和正常单链表中next指针的意义

一 样，都指向下一个节点，rand指针是Node类中新增的指针，这个指

针可 能指向链表中的任意一个节点，也可能指向null。 给定一个由

Node节点类型组成的无环单链表的头节点head，请实现一个 函数完成

这个链表中所有结构的复制，并返回复制的新链表的头节点。 进阶：

不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N)

内完成原问题要实现的函数。

Solution

一：

使用hash_map来进行存放原链表

key=原链表， value=新建链表的节点

然后根据原链表的结构将新链表进行结构构造

二：

将原链表数组原地复制两份：

head 1 2 3 4 5 6 NULL

复制成： head head' 1 1' 2 2' 3 3' 4 4' 5 5' 6' 6' NULL

然后Copy则取带'的节点就行

 

1 #pragma once  2 #include 
     
        3 #include 
      
         4   5 using namespace std;  6   7 struct Node  8 {  9     int val; 10     Node *rand; 11     Node *next; 12     Node(int a = -1) :val(a), rand(NULL), next(NULL) {} 13 }; 14  15  16 Node* CopeListDeep(Node* head) 17 { 18     hash_map
       
        map; 19     Node* p = head; 20     while (p)//新建链表的结构 21     { 22         map[p] = new Node(-1); 23         p = p->next; 24     } 25  26     p = head; 27     while (p)//重构新链表的结构 28     { 29         map[p]->val = p->val; 30         map[p]->next = map[p->next]; 31         map[p]->rand = map[p->rand]; 32         p = p->next; 33     } 34     return map[head]; 35 } 36  37 Node* CopeListDeep2(Node* head) 38 { 39     Node* cur = head; 40     Node* next = NULL; 41     while (cur)//将原链表复制两份 42     { 43         next = cur->next; 44         cur->next = new Node(cur->val); 45         cur->next->next = next;//此处为复制两份的代码 46         cur = next; 47     } 48  49     cur = head; 50     Node* copyHead = NULL;//为了区分原链 51     //先复制rand节点 52     while (cur)//将新建的节点的结构进行重构 53     { 54         next = cur->next->next;//原链表的遍历 55         copyHead = cur->next; 56         copyHead->rand = ((cur->rand) == NULL ? NULL : (cur->rand)->next); 57         cur = next; 58     } 59     //copyHead已经是链表的末尾NULL 60     cur = head; 61     Node* res = head->next; 62     while (cur) 63     { 64         next = cur->next->next; 65         copyHead = cur->next; 66         cur->next = next; 67         copyHead->next = (next == NULL) ? NULL : next->next; 68         cur = next; 69     } 70  71     //为什么不一次性将原链表进行还原和复制链表进行重构？ 72     //因为一旦原链表前半部分还原，而后半部分一旦有rand指向前半部分，原链表是能找到所指向 73     //的节点，但由于前半部分原链表已经还原了，所以复制链表的rand无法依据原链表的位置找到自己rand所指向的节点， 74     //故得先将rand  copy出来。 75     return res; 76  77 } 78  79  80 void Test() 81 { 82     Node *head = new Node(-1); 83     head->next = new Node(1); 84     head->next->next = new Node(2); 85     head->next->next->next = new Node(3); 86     head->next->next->next->next = new Node(4); 87     head->next->next->next->next->next = new Node(5); 88     head->next->next->next->next->next->next = new Node(6); 89     head->next->next->next->next->next->next->next = NULL; 90  91  92     head->rand = NULL; 93     head->next->rand = head->next->next->next->next->next->next; 94     head->next->next->rand = head->next->next->next->next->next->next; 95     head->next->next->next->rand = head->next->next->next->next->next; 96     head->next->next->next->next->rand = head->next->next->next; 97     head->next->next->next->next->next->rand = NULL; 98     head->next->next->next->next->next->next->rand = head->next->next->next->next; 99 100 101     cout << "打印原链表:" << endl;102     Node*p = head->next;103     while (p)104     {105         cout << "next: " << p->val << "   rand: " << ((p->rand) ? p->rand->val : -1) << endl;106         p = p->next;107     }108 109     cout << endl << "打印新链表:" << endl;110     p = CopeListDeep2(head)->next;111     while (p)112     {113         cout << "next: " << p->val << "   rand: " << ((p->rand) ? p->rand->val : -1) << endl;114         p = p->next;115     }116 117 118 }