广东品牌网站建设服务机构,wordpress禁止制定ip访问,工程信息造价,狮山网站建设公司对于无头单向不循环链表#xff0c;给出头结点head与数值val#xff0c;删除链表中数据值val的所有结点
#define ListNodeDataType val
struct ListNode
{ struct ListNode* psll;ListNodeDataType val;
}
方法一---遍历删除
移除所有数值为val的链表结点#xff0c;…对于无头单向不循环链表给出头结点head与数值val删除链表中数据值val的所有结点
#define ListNodeDataType val
struct ListNode
{ struct ListNode* psll;ListNodeDataType val;
}
方法一---遍历删除
移除所有数值为val的链表结点那么我们就需要遍历寻找val值为val的结点然后由于需要删除因此还需要前一个结点来链接删除结点的后一个结点。
我们创建prev与cur指针cur指针用于遍历寻找存储数值为val的结点prev指针用于链接下一个结点。 struct ListNode* prev NULL;struct ListNode* cur head;
优先讨论一般情况当cur-val与val相等时说明我们需要删除cur指向的结点那么我们需要先将prev指向结点中存储的next指针指向待删除结点的下一个结点cur-next即prev-nextcur-next然后再释放cur指向结点。由于释放完我们需要将cur指向后一个结点如果首结点val相等删除首结点那么如果不创建新指针指向后一个结点我们无法完成cur指向修改操作。
如果cur-val与val不相等那么我们就将prev与cur指针一前一后向后移动即可。 while(cur!NULL){if(cur-valval){struct ListNode* next cur-next;if(prev)prev-next next;elsehead cur-next;free(cur);cur next;}else{prev cur;curcur-next;}}return head;
如果prev为NULL那就说明首结点是待删除结点那么我们需要更改head指向不能再使用prev-next这是个空指针的非法访问。
整体代码如下
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prev NULL;struct ListNode* cur head;while (cur ! NULL){if (cur-val val){struct ListNode* next cur-next;free(cur);if (prev)prev-next next;elsehead next;cur next;}else{prev cur;cur cur-next;}}return head;
}
方法二---拿出不需要删除的结点放入新的链表
那么我们需要创建一个新的头指针anotherhead然后需要有一个指针变量cur2来遍历插入结点。 struct ListNode* cur1 head;struct ListNode* cur2 NULL;struct ListNode* anotherhead NULL;
我们通过cur1指针遍历原链表拿出不需要删除的结点如果是第一个不删除的结点那么就让anotherhead与cur2均指向该结点后面就动cur2即可anotherhead就能够保证不为NULL指向第一个不删除的结点空间。对于第一个不删除的结点转换为if条件就是cur2NULL或者anotherheadNULL当两者仍然是NULL而循环中进入了cur1-val ! val的if表达式那么就需要对头指针another和cur2两者进行赋值。cur1遍历到val值的结点就释放并记录下一个结点位置。 while (cur1){if (cur1-val ! val){if (cur2 NULL){anotherhead cur1;cur2 cur1;}else{cur2-next cur1;cur2 cur2-next;}cur1 cur1-next;}else{struct ListNode* prev cur1;cur1 cur1-next;free(prev);prev NULL;}}
但是循环结束并没有完成这个删除操作因为最后cur2指向的结点中的next指针的指向没有修改。也就是尾结点存储的next指针不一定为NULL我们需要在循环结束后将cur2-next置空。同时考虑周全如果给你的是一个空链表cur2-next岂不是非法访问因此还要进行一次if的条件判断cur2不为空时才将尾结点的next指针置空最后返回anotherhead或者把anotherhead赋给head返回head。 if (cur2 ! NULL)cur2-next NULL;return anotherhead;
方法三---创建哨兵位头结点newhead struct ListNode* newhead (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur2 newhead;
开辟一个哨兵位的空间好处是最后不用使用条件判断cur2是否为NULL因为cur2最不济也指向哨兵位不可能出现空指针的解引用操作当然坏处是最后由于要释放空间需要额外创建指针存放newhead-next地址释放newhead空间再返回我们的首结点地址。
大体与方法二其实差不多。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur1 head;struct ListNode* newhead (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur2 newhead;while (cur1){if (cur1-val ! val){cur2-next cur1;cur2 cur2-next;cur1 cur1-next;}else{struct ListNode* prev cur1;cur1 cur1-next;free(prev);prev NULL;}}cur2-next NULL;//下面释放开辟的哨兵位空间struct ListNode* tmp newhead;newhead newhead-next;free(tmp);tmp NULL;return newhead;
}
