删除链表中给定值val的所有节点@Leetcode —— 单链表

小题解

小边碎碎念：近日更新一波数据结构题解，可能不会像之前一样画很细的图了，因为真没那么多时间了。主要目的是复习一波，留个总结也方便日后复习。

1. 题目描述

题目链接 ：删除链表中给定值val的所有节点

2. 完整代码及注意小点

示例其实包含了所有你要考虑的情况，空链表、删头以及最最普通的中间节点的删除。

structListNode*removeElements(structListNode* head,int val){if(head ==NULL)returnNULL;structListNode* cur = head;while(cur !=NULL){if(cur->val == val){if(cur == head){// 1.头结点刚好要删structListNode* headNext = head ->next;
                cur = cur->next;free(head);
                head = headNext;}else{// 2.删除中间节点structListNode* curPrev = head;structListNode* curNext = cur->next;// 找cur的上一个节点，此时肯定至少有一个节点while(curPrev->next != cur){
                    curPrev = curPrev->next;}
                curPrev->next = curNext;free(cur);
                cur = curNext;}}else{
            cur = cur->next;}}return head;}

注

1. 删除头的部分 即头结点刚好等于val，要先把cur迭代，再释放head。因为这时cur和head实际上等同，释放head后，head（即cur）中的val和next都会变成随机值，因此要先记录。

3. 反思

对比其他题解，思路大同小异，但还是有值得反思的地方，如下

1. 中间节点的删除部分 关于记录上一节点curPrev，它采取了实时记录，curPrev一直跟着cur，毕竟在这里cur会进行一个遍历，curPrev跟着走是顺理成章的，不该没想到。而我每次都从头开始找（这种习惯可能来自于根深蒂固的尾插思路），思路很简单，但也很粗暴，这一定程度上增加了时间复杂度。并且如果头脑不够清醒，确实搞得整个逻辑好像很复杂一样。

于是，我看了个大概之后又写了一遍，哎呦，发现因为上面一小事，就一整个清晰很多。

structListNode*removeElements(structListNode* head,int val){structListNode* curPrev =NULL;structListNode* cur = head;while(cur !=NULL){if(head->val == val){// 处理头删
            head = head->next;free(cur);
            cur = head;}elseif(cur ->val == val){
            curPrev->next = cur->next;free(cur);
            cur = curPrev->next;}else{
            curPrev = cur;
            cur = cur->next;}}return head;}

持续更新@边通书