想法一
创建prev和cur两个指针，如果cur指向的元素的值为val，则删除，如果不为val，则prev和cur各自往后一个节点
注意：删除时要考虑第一个元素是不是val，如果是，则为头删，如果不是，则为指定删除（不分类则会造成对prev空指针的解引用）
同样，不删除时，也要分prev是否为NULL的情况
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode *cur = head, *prev = NULL; while (cur) { if (cur->val == val) { if (prev) { //指定删除 prev->next = cur->next; free(cur); cur = prev->next; } else { //头删 prev = cur; cur = cur->next; free(prev); prev = NULL; head = cur; } } else { if(prev) { prev = prev->next; } else { prev = cur; } cur = cur->next; } } return head; }
想法二
其实还有一种方式可以避免删除，那就是，可以生成一个新链表头newhead，遍历链表，把不是val的元素拿来尾插
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newhead = NULL; struct ListNode* prev = NULL; struct ListNode* cur = head; while (cur) { if (cur->val == val) { if (prev) { prev->next = cur->next; } cur = cur->next; } else { if (prev) { prev = prev->next; } else { newhead = cur; prev = cur; } cur = cur->next; } } return newhead; }
不过其实并没有比想法一好多少，同样要分prev是不是NULL讨论，两种方法都差不多，主要是思路上有细微的差别
总结
在链表的题目里，要特别注意对空指针和野指针的判断，大多数人也在这里经常犯错。
