笔试常考的数据结构-单链表操作实现.doc

笔试常考的数据结构-单链表操作实现单链表是笔试以及面试手写代码中常考的数据结构之一。下面实现了单链表的常见操作：创建单链表、删除节点、打印单链表（包括正向打印以及逆向打印）、反转单链表、找出单链表的倒数第K个节点、合并两个有序单链表等操作。代码（C+）：1. /笔试面试单链表常用操作编程实现 2. #include 3. #include 4. #include 5.6. using namespace std; 7.8. /单链表节点数据结构定义 9. typedef struct link_node_s 10. int m_val; 11. struct link_node_s *next; 12. link_node_t,*link_list_t; 13.14. /函数:创建单链表(头插法) 15. link_list_t create_linklist(int *a,int n); 16.17. /函数:打印单链表(从头到尾) 18. void print_linklist(link_list_t head); 19.20. /函数:打印单链表(从尾到头) 21. void print_linklist_reverse(link_list_t head); 22.23. /函数:新建链表节点 24. link_list_t creart_linknode(int val); 25.26. /函数:删除链表中的某一个节点(前提条件:该节点一定存在) 27. /性能要求:在O(1)时间复杂度内实现 28. void delete_node_exist(link_list_t *head,link_list_t node_deleted); 29.30. /函数:删除链表中数据值等于给定值的节点 31. void delete_node(link_list_t *head,int val); 32.33. /函数:获得链表中的倒数第K个节点 34. link_list_t get_kth_node(link_list_t head,int k); 35.36. /函数:反转链表 37. link_list_t reverse_linklist(link_list_t head); 38.39. /函数:合并两个已排序的链表(递归方法实现) 40. link_list_t merge_linklist_recursive(link_list_t head1,link_list_t head2); 41.42. int main() 43. const int num1 = 8; 44. const int num2 = 10; 45. int *a = new intnum1; 46. int *b = new intnum2; 47. int *a_sorted = new intnum1; 48. int *b_sorted = new intnum2; 49.50. srand(1); 51. for(int i = 0;i num1;+i) 52. *(a + i) = rand() % 100; 53. *(a_sorted + i) = 50 - i * 2 + 8; 54. 55.56. for(int i = 0;i num2;+i) 57. *(b + i) = rand() % 200; 58. *(b_sorted + i) = 50 - i * 4 + 1; 59. 60.61. cout *创建链表测试* endl; 62. link_list_t list1 = create_linklist(a,num1); 63. link_list_t list2 = create_linklist(b,num2); 64. link_list_t list_sorted1 = create_linklist(a_sorted,num1); 65. link_list_t list_sorted2 = create_linklist(b_sorted,num2); 66.67. cout *输出链表测试(正向输出)* endl; 68. cout 链表1: endl; 69. print_linklist(list1); 70. cout 链表1(已序): endl; 71. print_linklist(list_sorted1); 72. cout 链表2(已序): endl; 73. print_linklist(list_sorted2); 74.75. cout *输出链表测试(逆向输出)* endl; 76. print_linklist_reverse(list1); 77.78.79. cout *获取链表的倒数第K个节点测试* endl; 80. int k = 3; 81. link_list_t kth_node = get_kth_node(list1,k); 82. if(NULL = kth_node) 83. cout 链表中倒数第 k 个节点不存在 endl; 84. else 85. cout 链表中倒数第 k 个节点是: m_val endl; 86.87. k = 8; 88. kth_node = get_kth_node(list1,k); 89. if(NULL = kth_node) 90. cout 链表中倒数第 k 个节点不存在 endl; 91. else 92. cout 链表中倒数第 k 个节点是: m_val endl; 93.94. k = 11; 95. kth_node = get_kth_node(list1,k); 96. if(NULL = kth_node) 97. cout 链表中倒数第 k 个节点不存在 endl; 98. else 99. cout 链表中倒数第 k 个节点是: m_val endl; 100.101. cout *删除链表中一定存在的节点测试(输入参数是要删除的节点指针)* m_val != *(a + 4) 104. node_deleted = node_deleted-next; 105.106. cout 删除节点 *(a + 4) 之后的单链表: m_val != *(a + 6) 112. node_deleted = node_deleted-next; 113.114. cout 删除节点 *(a + 6) 之后的单链表: endl; 115. delete_node_exist(&list1,node_deleted); 116. print_linklist(list1); 117.118. cout *删除链表中值等于给定值的节点测试(不一定存在,输入参数是int型值)* endl; 119. const int val_deleted = 22; 120. delete_node(&list1,val_deleted); 121. cout 删除值等于 val_deleted 之后的链表: endl; 122. print_linklist(list1); 123.124. cout *合并链表测试* endl; 125. link_list_t merge_list_head = merge_linklist_recursive(list_sorted1,list_sorted2); 126. print_linklist(merge_list_head); 127.128.129. cout *逆转链表测试* endl; 130. link_list_t head_reverse = reverse_linklist(merge_list_head); 131. cout 逆转之后的链表: endl; 132. cout 头节点: m_val endl; 133. print_linklist(head_reverse); 134.135. return 0; 136. 137.138. /函数:创建单链表(头插法) 139. link_list_t create_linklist(int *a,int n) 140. link_list_t head = NULL; 141.142. if(NULL = a | 0 = n) 143. return NULL; 144.145. for(int i = 0;i next = head; 153. head = new_node; 154. 155. 156.157. return head; 158. 159.160. /函数:新建链表节点 161. link_list_t creart_linknode(int val) 162. link_list_t node = new link_node_t; 163. node-m_val = val; 164. node-next = NULL; 165.166. return node; 167. 168.169. /函数:打印单链表 170. void print_linklist(link_list_t head) 171. link_list_t node = head; 172.173. cout 正向输出单链表 endl; 174. while(node != NULL) 175. cout m_val next; 177. 178. cout endl; 179.180. return; 181. 182.183. /函数:打印单链表(从尾到头) 184. void print_linklist_reverse(link_list_t head) 185. stack node_stack; 186. link_list_t node = head; 187. while(node != NULL) 188. node_stack.push(node-m_val); 189. node = node-next; 190. 191.192. cout 逆向输出单链表 endl; 193. while(!node_stack.empty() 194. cout node_stack.top() ; 195. node_stack.pop(); 196. 197. cout next != NULL) 214. link_list_t next_node = node_deleted-next; 215. node_deleted-m_val = next_node-m_val; 216. node_deleted-next = next_node-next; 217.218. delete next_node; 219. next_node = NULL; 220. 221. /链表中只有一个节点 222. else if(*head = node_deleted) 223. delete node_deleted; 224. node_deleted = NULL; 225. *head = NULL; 226. 227. /要删除的节点是尾节点 228. else 229. link_list_t node = *head; 230. while(node-next != node_deleted) 231. node = node-next; 232.233. node-next = node_deleted-next; 234. delete node_deleted; 235. node_deleted = NULL; 236. 237.238. return; 239. 240.241. /函数:获得链表中的倒数第K个节点 242. link_list_t get_kth_node(link_list_t head,int k) 243. /性能:只需遍历链表一遍即可 244. /算法思想:设置两个指针,一个指向链表头部,一个指向第k个节点,然后两个指针同时向后移动,当第二个指针指向链表的尾节点时,第一个指针指向的节点便是倒数第K个节点 245. /注意代码的鲁棒性,防止程序的崩溃 246. if(NULL = head | k = 0) 247. return NULL; 248.249. /设置两个指针 250. link_list_t p1 = head,p2 = head; 251. int i = 0; 252. /第二个指针向前走k-1步 253. while(i next != NULL) 254. p2 = p2-next; 255. +i; 256. 257. /注意链表中总节点数小于K的情况 258. if(i != k - 1 & NULL = p2-next) 259. return NULL; 260.261. /两个指针同时向后前进 262. while(p2-next != NULL) 263. p1 = p1-next; 264. p2 = p2-next; 265. 266.267. return p1; 268. 269.270.271. /函数:反转链表 272. /返回值:反转之后的链表头节点 273. link_list_t reverse_linklist(link_list_t head) 274. /链表为空或者只有一个节点 275. if(NULL = head | NULL = head-next) 276. return head; 277.278. link_list_t prev_node = NULL,next_node,cur_node = head,head_reverse; 279. while(cur_node != NULL) 280. next_node = cur_node-next; 281. if(NULL = next_node) 282. head_reverse = cur_node;/原链表尾节点即逆转后链表的头节点 283. cur_node-next = prev_node; 284. prev_node = cur_node; 285. cur_node = next_node; 286. 287.288. return head_reverse; 289. 290.291. /函数:删除链表中数据值等于给定值的节点 292. void delete_node(link_list_t *head,int val) 293. if(NULL = head) 294. cout Delete node failed :The node to be delete not exist! m_val) 299. link_list_t node = *head; 30