對于無頭單向不循環(huán)鏈表，給出頭結點head與數(shù)值val，刪除鏈表中數(shù)據(jù)值=val的所有結點

#define ListNodeDataType val 
struct ListNode
{    struct ListNode* psll;ListNodeDataType val;
}

方法一---遍歷刪除

移除所有數(shù)值為val的鏈表結點，那么我們就需要遍歷尋找val值為val的結點，然后由于需要刪除，因此還需要前一個結點來鏈接刪除結點的后一個結點。

我們創(chuàng)建prev與cur指針，cur指針用于遍歷尋找存儲數(shù)值為val的結點，prev指針用于鏈接下一個結點。

    struct ListNode* prev = NULL;struct ListNode* cur = head;

優(yōu)先討論一般情況，當cur->val與val相等時，說明我們需要刪除cur指向的結點，那么我們需要先將prev指向結點中存儲的next指針指向待刪除結點的下一個結點cur->next，即prev->next=cur->next，然后再釋放cur指向結點。由于釋放完我們需要將cur指向后一個結點，如果首結點val相等，刪除首結點，那么如果不創(chuàng)建新指針指向后一個結點我們無法完成cur指向修改操作。

如果cur->val與val不相等，那么我們就將prev與cur指針一前一后向后移動即可。

    while(cur!=NULL){if(cur->val==val){struct ListNode* next = cur->next;if(prev)prev->next = next;elsehead = cur->next;free(cur);cur = next;}else{prev = cur;cur=cur->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;
}

方法二---拿出不需要刪除的結點放入新的鏈表

那么我們需要創(chuàng)建一個新的頭指針anotherhead，然后需要有一個指針變量cur2來遍歷插入結點。

    struct ListNode* cur1 = head;struct ListNode* cur2 = NULL;struct ListNode* anotherhead = NULL;

我們通過cur1指針遍歷原鏈表，拿出不需要刪除的結點，如果是第一個不刪除的結點那么就讓anotherhead與cur2均指向該結點，后面就動cur2即可，anotherhead就能夠保證不為NULL，指向第一個不刪除的結點空間。對于第一個不刪除的結點，轉(zhuǎn)換為if條件就是cur2==NULL或者anotherhead==NULL，當兩者仍然是NULL，而循環(huán)中進入了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;}}

但是循環(huán)結束并沒有完成這個刪除操作，因為最后cur2指向的結點中的next指針的指向沒有修改。也就是尾結點存儲的next指針不一定為NULL，我們需要在循環(huán)結束后將cur2->next置空。同時，考慮周全，如果給你的是一個空鏈表，cur2->next豈不是非法訪問？因此還要進行一次if的條件判斷，cur2不為空時才將尾結點的next指針置空，最后返回anotherhead或者把anotherhead賦給head返回head。

    if (cur2 != NULL)cur2->next = NULL;return anotherhead;

方法三---創(chuàng)建哨兵位頭結點newhead

    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur2 = newhead;

開辟一個哨兵位的空間，好處是最后不用使用條件判斷cur2是否為NULL，因為cur2最不濟也指向哨兵位，不可能出現(xiàn)空指針的解引用操作；當然壞處是，最后由于要釋放空間需要額外創(chuàng)建指針存放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;
}