刷题笔记:力扣第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，因为只关心真实节点中的数值。