【说明】:
本文是左程云老师所著的《程序员面试代码指南》第二章中“复制含有随机指针节点的链表”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
一种特殊的链表节点类描述如下:
1 struct Node
2 12 {
3 13 int value;
4 14 Node *next;
5 15 Node *rand;
6 16 };
View Code
Node 中的 value 是节点值,next 指针和正常链表中的 next 指针的意义一样,都指向下一个节点,rand 指针是 Node 类中新增的指针,这个指针可能指向链表中的任意一个节点,也可能指向 NULL。
给定一个由 Node 节点类型组成的无环单链表的头节点 head,请实现一个函数完成这个链表中所有结构的复制,并返回复制的新链表的头节点。例如:链表1->2->3->NULL。假设 1 的 rand 指针指向 3,2 的 rand 指针指向NULL,3 的 rand 指针指向 1。复制后的链表应该也是这种结构,比如, 1‘-2'->3'->NULL,1' 的 rand 指针指向 3,2' 的 rand 指针指向 NULL,3' 的 rand 指针指向 1‘,最后返回 1‘。
【进阶】:
不是用额外的数据结构,只使用有限几个变量,且在时间复杂度为 O(N)内完成原问题要实现的函数。
【思路】:
普通解法:使用hash_map
进阶解法:1->2->3-NULL ------> 1->1'->2->2'->3->3'->NULL
不管是普通算法还是进阶算法找到 rand 所对应的 Node 是关键。
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
实现及测试代码:
1 /*
2 *文件名:listWithRand_copy.cpp
3 *作者:
4 *摘要:复制含有随机指针节点的链表
5 */
6
7 #include <iostream>
8 #include <hash_map>
9
10 using namespace std;
11 using namespace __gnu_cxx;
12
13 struct Node
14 {
15 int value;
16 Node *next;
17 Node *rand;
18 };
19
20 //使用hash_map所需要的hash函数
21 struct hash_Node
22 {
23 size_t operator() (const Node &node) const
24 {
25 return node.value;
26 }
27 };
28
29 //使用hash_map所需要的比较函数
30 struct compare_Node
31 {
32 bool operator() (const Node &n1,const Node &n2) const
33 {
34 return n1.value == n2.value && n1.next == n2.next && n1.rand == n2.rand;
35 }
36 };
37
38 //使用hash_map解决问题
39 Node* copyListWithRand1(Node *head)
40 {
41 hash_map<Node,Node,hash_Node,compare_Node> map;
42 Node *cur = head;
43 while(NULL != cur)
44 {
45 Node *ptr = new Node;
46 ptr->value = cur->value;
47 ptr->next = NULL;
48 ptr->rand = NULL;
49 map[*cur] = *ptr; //一一对应的关系
50 cur = cur->next;
51 }
52 cur = head;
53 while(NULL != cur)
54 {
55 map[*cur].next = cur->next;
56 map[*cur].rand = cur->rand;
57 cur = cur->next;
58 }
59 return &map[*head];
60 }
61
62 Node* copyListWithRand2(Node *head)
63 {
64 if(NULL == head)
65 return NULL;
66 Node *cur = head;
67 Node *next = NULL;
68 while(NULL != cur)
69 {
70 next = new Node;
71 next->value = cur->value;
72 next->next = cur->next;
73 next->rand = NULL;
74 cur->next = next;
75 cur = next->next;
76 }
77
78 cur = head;
79 Node *curCopy = NULL;
80 while(NULL != cur) //复制rand
81 {
82 next = cur->next->next;
83 curCopy = cur->next;
84 curCopy->rand = NULL != cur->rand ? cur->rand->next : NULL;
85 cur = next;
86 }
87
88 Node *res = head->next;
89 cur = head;
90 while(NULL != cur)
91 {
92 next = cur->next->next;
93 curCopy = cur->next;
94 cur->next = next;
95 curCopy->next = NULL != next ? next->next : NULL;
96 cur = next;
97 }
98 return res;
99 }
100
101 void printListWithRand(Node *head)
102 {
103 while(NULL != head)
104 {
105 if(NULL != head->rand)
106 cout << head->value << " rand is: " << head->rand->value << endl;
107 else
108 cout << head->value << " rand is: NULL " << endl;
109
110 if(NULL != head->next)
111 cout << head->value << " next is: " << head->next->value << endl;
112 else
113 cout << head->value << " next is: NULL " << endl;
114 head = head->next;
115 }
116 }
117
118 int main()
119 {
120 Node *head = NULL;
121 Node *ptr = NULL;
122
123 for(int i =0;i<4;i++)//构造链表
124 {
125 if(NULL == head)
126 {
127 head = new Node;
128 head->value = i;
129 head->next = NULL;
130 head->rand = NULL;
131 ptr = head;
132 continue;
133 }
134 ptr->next = new Node;
135 ptr->rand = ptr->next;
136 ptr = ptr->next;
137 ptr->value = i;
138 ptr->next = NULL;
139 ptr->rand = NULL;
140 }
141
142 cout << "before copy:" << endl;
143 printListWithRand(head);
144
145 cout << "Using hash_map to copy:" << endl;
146 ptr = copyListWithRand1(head);
147 printListWithRand(ptr);
148
149 cout << "Using advanced algorithm to copy:" << endl;
150 ptr = copyListWithRand2(head);
151 printListWithRand(ptr);
152 return 0;
153 }
View Code
【说明】
关于hash_map的使用,依然请参考[Z]C++ STL中哈希表 hash_map介绍
使用 struct 来声明节点貌似不太符合C++哈,下次开始使用 class 来声明
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5374358.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231701
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!