题目要求
链接：https://leetcode-cn.com/problems/remove-linked-list-elements/description/
解题思路
遍历链表进行对比，判断是不是要删除的结点
要保存释放结点的下一个结点，所以要定义两个指针。不然就找不到下一个结点了
cur：用于遍历链表，初始化 ： 指向头结点
prev ：保存cur的上一个结点 初始化为：NULL
- 如果cur指向的是要删除的结点：
- 先保存下一个结点 prev->next = cur->next
- 释放cur指向的结点 free(cur)
- 然后把cur指向下一个结点 cur = prev->next （prev->next就是原来cur的下一个结点）
- 如果cur指向的不是要删的结点：prev和cur迭代往后走
- prev保存现在cur的位置 prev = cur
- cur指向下一个位置 cur = cur -> next
特殊情况：要删除的是头结点
- 此时要释放原来的头结点，然后更改头指针的指向
- 步骤：
- 1.先保存头结点的下一个位置 cur = cur->next
- 2.释放头结点 free(head)
- 3.更改头指针的指向：head = cur
或者：
head = cur->next;//换头 free(cur);//释放原来的头结点 cur = head;//cur指向新的头
错误写法：
free(head); head = cur->next; cur = head;
错误原因：
提前释放了头结点，已经找不到它的下一个位置了
cur -> next 是野指针
代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ //链表为空，返回空 if(head == NULL) { return NULL; } //定义两个指针，cur用于遍历，prev用于保存cur的上一个结点 struct ListNode* prev = NULL;//若prev最初也指向head是有风险的 struct ListNode* cur = head; while(cur) { //如果cur指向的是要删的元素 if(cur->val == val) { //特殊情况：要删的是头 if(cur == head) { //释放原来的头结点，换头 head = cur->next;//换头 free(cur);//释放原来的头结点 cur = head;//cur指向新的头 } else { prev->next = cur->next;//保存下一个结点 free(cur);//释放cur指向结点 cur = prev->next;//cur指向下一个结点 } } //如果cur指向的不是要删除的元素 else { //prev保存的是cur的前一个结点 prev = cur;//prev指向cur cur = cur->next;//cur迭代往后走 } } return head; }
prev若初始化为head的风险
为了保险起见：最初 prev = NULL
错误写法
和上面的不同点:
当cur指向的是要删除的结点时：
- 用prev保存cur的下一个结点
下面正确写法是：用prev->next指向cur的下一结点
struct ListNode* removeElements(struct ListNode* head, int val){ //链表为空，返回空 if(head == NULL) { return NULL; } //定义两个指针，cur用于遍历，prev用于保存cur的上一个结点 struct ListNode* prev = NULL;//若prev最初也指向head是有风险的 struct ListNode* cur = head; while(cur) { //如果cur指向的是要删的元素 if(cur->val == val) { //特殊情况：要删的是头 if(cur == head) { //释放原来的头结点，换头 head = cur->next;//换头 free(cur);//释放原来的头结点 cur = head;//cur指向新的头 } else { prev = cur->next;//保存下一个结点 ->有问题！！！！！！！ free(cur);//释放cur指向结点 cur = prev->next;//cur指向下一个结点 } } //如果cur指向的不是要删除的元素 else { prev = cur;//prev指向cur cur = cur->next;//cur迭代往后走 } } return head; }
错误原因：