刷题笔记:力扣第707题-设计链表

1.本题是一道链表综合性题目基本上将链表的所有操作全都考察了一遍以下是写出的完整代码1. typedef struct MyLinkedList{ 2. int val; 3. struct MyLinkedList* next; 4. } MyLinkedList; 5. 6. // 创建链表初始化虚拟头节点 7. MyLinkedList* myLinkedListCreate() { 8. // 分配虚拟头节点内存 9. struct MyLinkedList* dummyHead (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList)); 10. // 初始链表无有效节点虚拟头后继置空 11. dummyHead-next NULL; 12. return dummyHead; 13. } 14. 15. // 获取下标index位置节点的值无节点返回-1 16. int myLinkedListGet(MyLinkedList* obj, int index) { 17. // cur指向第一个真实节点 18. struct MyLinkedList* cur obj-next; 19. // 循环移动index次到达目标下标 20. for (int i 0; i index; i){ 21. // 中途链表断裂下标越界直接返回-1 22. if (cur NULL){ 23. return -1; 24. } 25. cur cur-next; 26. } 27. // 循环结束cur为空说明下标不存在返回-1否则返回节点值 28. return cur NULL ? -1 : cur-val; 29. } 30. 31. // 在链表头部插入节点 32. void myLinkedListAddAtHead(MyLinkedList* obj, int val) { 33. // 新建待插入节点 34. struct MyLinkedList* newHead (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList)); 35. // 新节点后继指向原第一个有效节点 36. newHead-next obj-next; 37. // 设置节点存储数值 38. newHead-val val; 39. // 虚拟头指向新节点完成头插 40. obj-next newHead; 41. } 42. 43. // 在链表尾部插入节点 44. void myLinkedListAddAtTail(MyLinkedList* obj, int val) { 45. // 创建新尾节点 46. struct MyLinkedList* newTail (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList)); 47. // 遍历指针从虚拟头出发 48. struct MyLinkedList* cur obj; 49. // 循环找到链表最后一个节点 50. while (cur-next ! NULL){ 51. cur cur-next; 52. } 53. // 尾节点后继为空 54. newTail-next NULL; 55. newTail-val val; 56. // 原尾节点连接新节点 57. cur-next newTail; 58. } 59. 60. // 在下标index位置插入节点 61. void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) { 62. // 遍历指针从虚拟头开始 63. struct MyLinkedList* cur obj; 64. // 移动index次找到插入位置的前驱节点 65. for (int i 0; i index; i){ 66. // 中途指针为空下标非法直接退出 67. if (cur NULL){ 68. return; 69. } 70. cur cur-next; 71. } 72. // 前驱为空无插入位置直接返回 73. if (cur NULL){ 74. return; 75. } else { 76. // 新建插入节点 77. struct MyLinkedList* newNode (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList)); 78. // 新节点连接原index位置节点 79. newNode-next cur-next; 80. newNode-val val; 81. // 前驱节点指向新节点完成插入 82. cur-next newNode; 83. } 84. 85. } 86. 87. // 删除下标index位置的节点 88. void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) { 89. // 遍历指针从虚拟头出发 90. struct MyLinkedList* cur obj; 91. // 移动index次找到待删节点的前驱 92. for (int i 0; i index; i){ 93. // 指针为空下标非法直接退出 94. if (cur NULL){ 95. return; 96. } 97. cur cur-next; 98. } 99. // 前驱为空 / 前驱无后继说明目标节点不存在直接返回 100. if (cur NULL || cur-next NULL){ 101. return; 102. } else { 103. // 保存待删除节点地址 104. struct MyLinkedList* del cur-next; 105. // 前驱跳过待删节点重新连接链表 106. cur-next cur-next-next; 107. // 释放被删除节点内存 108. free(del); 109. } 110. } 111. 112. // 释放整个链表所有节点内存 113. void myLinkedListFree(MyLinkedList* obj) { 114. // cur指向第一个真实节点 115. struct MyLinkedList* cur obj-next; 116. // 循环销毁每一个有效节点 117. while (cur ! NULL){ 118. // 缓存当前待释放节点 119. struct MyLinkedList* del cur; 120. // 指针先后移防止断链丢失后续节点 121. cur cur-next; 122. free(del); 123. } 124. // 最后释放虚拟头节点 125. free(obj); 126. } 127. 128. /** 129. * Your MyLinkedList struct will be instantiated and called as such: 130. * MyLinkedList* obj myLinkedListCreate(); 131. * int param_1 myLinkedListGet(obj, index); 132. 133. * myLinkedListAddAtHead(obj, val); 134. 135. * myLinkedListAddAtTail(obj, val); 136. 137. * myLinkedListAddAtIndex(obj, index, val); 138. 139. * myLinkedListDeleteAtIndex(obj, index); 140. 141. * myLinkedListFree(obj); 142. */2.本道题目思想不难难点在于诸多小细节所以花费了很长时间下面是一些心得1能使用虚拟头结点就使用虚拟头结点这样能简化许多操作。2指针越界问题一定要注意在移动cur指针的时候考虑要所有的情况例如链表没有任何节点的特殊情况这时候使用虚拟头结点就能保证至少有一个真实节点代码就会更容易写出来。3执行链表全部删除操作时不要忘记释放虚拟头结点的空间。4当需要修改链表结构插入、删除时一般令cur dummyHead因为需要拿到index的上一个节点而0号节点的上一个节点正是dummyHead。5当只需要读取数据不改变链表结构时一般令cur dummyHead-next因为只关心真实节点中的数值。