刷题笔记:力扣第203题-移除链表元素

1.从实例中也可看到测试案例中可能会删除头节点所以应该引入虚拟头结点。以下是写出的完整代码1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. struct ListNode* removeElements(struct ListNode* head, int val) { 9. // 创建虚拟头节点统一处理链表头部节点需要删除的情况 10. struct ListNode* dummyHead (struct ListNode*)malloc(sizeof(struct ListNode)); 11. // 虚拟头节点指向原链表头 12. dummyHead-next head; 13. // cur遍历指针从虚拟头节点开始 14. struct ListNode* cur dummyHead; 15. 16. // 遍历整条链表 17. while (cur ! NULL){ 18. // 判断当前节点的下一个节点值等于待删除值 19. if (cur-next ! NULL cur-next-val val){ 20. // 保存当前基准节点用来拼接删除后的链表 21. struct ListNode* tmp cur; 22. // 指针移动到待删除节点 23. cur cur-next; 24. // 连续跳过所有值等于val的节点 25. while (cur ! NULL cur-val val){ 26. cur cur-next; 27. } 28. // 基准节点直接连接到第一个不等于val的节点完成批量删除 29. tmp-next cur; 30. } else { 31. // 下一个节点无需删除指针向后移动 32. cur cur-next; 33. } 34. } 35. 36. // 返回删除完成后的链表真正头节点 37. return dummyHead-next; 38. }2.在写代码的时候出现了三个问题1struct ListNode* dummyHead (struct ListNode*)malloc(sizeof(struct ListNode))在定义时忘记添加struct前缀只写了ListNode。2tmp-next cur处写成tmp cur导致未实现断开链条连接到新的节点的目的tmp指针一直跟着cur移动没有起到该有的作用。3struct ListNode* cur dummyHead定义cur指针应该置于虚拟头结点处如果置于真实头结点处会导致漏掉处理真实头结点等于目标值的情况。3.写链表题目的时候应该保持释放不需要节点空间的好习惯即加入free。以下是修正后的完整代码1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. struct ListNode* removeElements(struct ListNode* head, int val) { 9. // 创建虚拟头节点统一处理头部节点需要删除的边界情况 10. struct ListNode* dummyHead (struct ListNode*)malloc(sizeof(struct ListNode)); 11. // 虚拟头节点指向原链表头部 12. dummyHead-next head; 13. // 遍历指针从虚拟头节点开始 14. struct ListNode* cur dummyHead; 15. 16. // 当下一个节点存在时循环遍历 17. while (cur-next ! NULL){ 18. // 如果下一个节点的值等于要删除的值 19. if (cur-next-val val){ 20. // tmp指针定位到第一个待删除节点 21. struct ListNode* tmp cur-next; 22. // 循环连续删除所有值等于val的节点 23. while (tmp ! NULL tmp-val val){ 24. // 保存当前待释放节点 25. struct ListNode* del tmp; 26. // tmp移动到下一个节点 27. tmp tmp-next; 28. // 释放被删除节点的内存避免内存泄漏 29. free(del); 30. } 31. // 当前节点直接连接到第一个不为val的节点完成批量删除 32. cur-next tmp; 33. } else { 34. // 下一个节点不需要删除指针向后移动 35. cur cur-next; 36. } 37. } 38. 39. // 返回处理后链表的真实头节点 40. return dummyHead-next; 41. }