左神算法基础班3_13深度拷贝含有随机指针的链表
标签：题目 变量 end 返回 深度 problem mes 组成 int
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_mapmap;
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: " val " rand: " rand) ? p->rand->val : -1) endl;
106 p = p->next;
107 }
108
109 cout "打印新链表:" endl;
110 p = CopeListDeep2(head)->next;
111 while (p)
112 {
113 cout "next: " val " rand: " rand) ? p->rand->val : -1) endl;
114 p = p->next;
115 }
116
117
118 }
左神算法基础班3_13深度拷贝含有随机指针的链表
标签：题目 变量 end 返回 深度 problem mes 组成 int
原文地址：https://www.cnblogs.com/zzw1024/p/10993026.html
评论