arcengine网站开发网站内容添加

对于无头单向不循环链表，给出头结点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->next=cur->next，然后再释放cur指向结点。由于释放完我们需要将cur指向后一个结点，如果首结点val相等，删除首结点，那么如果不创建新指针指向后一个结点我们无法完成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;
}

方法二---拿出不需要删除的结点放入新的链表

那么我们需要创建一个新的头指针anotherhead，然后需要有一个指针变量cur2来遍历插入结点。

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

我们通过cur1指针遍历原链表，拿出不需要删除的结点，如果是第一个不删除的结点那么就让anotherhead与cur2均指向该结点，后面就动cur2即可，anotherhead就能够保证不为NULL，指向第一个不删除的结点空间。对于第一个不删除的结点，转换为if条件就是cur2==NULL或者anotherhead==NULL，当两者仍然是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;
}