一、题目
函数原型：
struct ListNode* removeElements(struct ListNode* head, int val)
二、思路
本题有两种思路：
思路1
遍历单链表，如果遇到值为val的结点，则将该结点删除。
注意：当删除结点时，如果出现头结点为要删除的结点，那么prev->next就是对NULL进行解引用，所以这种情况需要先删除头结点，下一个结点作为新的头结点。
思路2
设置一个新的链表，遍历原有链表，如果遇到值不为val的结点，则将该结点尾插到新链表上，最终返回新链表。
思路2有两种实现方法，一种是带哨兵位的链表，另一种是不带哨兵位的链表
三、代码实现
思路1代码
/** * 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; while(head&&head->val==val)//先删除符合删除条件的头结点 { struct ListNode *tmp=head; head=head->next; free(tmp); } struct ListNode *prev=NULL;//定义前一指针，便于删除结点 struct ListNode *cur=head;//定义遍历指针 while(cur) { if(cur->val==val)//结点值等于val，删除结点 { prev->next=cur->next; free(cur); cur=prev->next; } else//结点值不等于val，跳过结点 { prev=cur; cur=cur->next; } } return head; }
思路2代码（不带哨兵位）
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode *cur=head;//遍历指针 struct ListNode *newhead=NULL;//新的头结点 struct ListNode *tail=newhead;//初始时尾指针指向新的头结点 while(cur)//开始遍历原链表 { if(cur->val!=val)//原链表结点值不等于val { if(tail==NULL)//初始时新链表为空，需要将要插入的结点作为新的头结点 { newhead=tail=cur; } else//新链表不为空，进行尾插 { tail->next=cur; tail=cur; } cur=cur->next; } else//销毁原链表中不需要的结点 { struct ListNode *tmp=cur; cur=cur->next; free(tmp); } if(tail)//关键点，尾结点的指针域指向空 tail->next=NULL; } return newhead; }
思路2代码（带哨兵位）
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode *newhead=NULL; struct ListNode *tail=NULL; //哨兵位 newhead=(struct ListNode *)malloc(sizeof(struct ListNode)); tail=newhead;//初始时，尾指针指向哨兵位 struct ListNode *cur=head;//遍历指针 while(cur)//开始遍历原链表 { if(cur->val!=val)//有哨兵位，直接进行尾插，无需判断头结点是否为空 { tail->next=cur; tail=cur; cur=cur->next; } else//销毁原链表中不需要的结点 { struct ListNode *tmp=cur; cur=cur->next; free(tmp); } } tail->next=NULL;//关键点，新链表尾结点的指针域指向空 //销毁哨兵位 struct ListNode *tmp=newhead; newhead=newhead->next; free(tmp); return newhead;//返回新链表的头结点 }
