【LeetCode】移除链表元素

题目链接：力扣

思路一：

这里我定义了一个cur和一个prev

先让它们同时指向head

再让cur往后走，没碰到val值就把cur赋给prev，碰到val值就把prev->next=cur->next之后再free（cur），然后再将cur=prev->next继续往后走

如果头部就是我们要删除的val值，我们还需要弄一个头删。 

循环当cur为NULL时停止。

代码如下：

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prev=NULL;struct ListNode* cur=head;while(cur){     if(cur->val==val)    { //头删 if(cur==head)//if(prev==NULL) {     head=cur->next;     free(cur);     cur=head; } else  {      //删除     prev->next=cur->next;     free(cur);     cur=prev->next; }    }    else    { prev=cur; cur=cur->next;    }}return head;}

思路二： 

遍历原链表，把不是val的节点拿出来尾插到新链表，最后返回新链表的头。

同样的我在这里定义的一个tail用于找尾，还有一个cur用来遍历原链表 

  当不是val值时，就给tail

更新tail 

  到最后还要把tail->next=NULL,否则会报错。

还有一个问题，当cur=head时，要把head=NULL，不然会有野指针问题。

 代码如下：

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* tail=NULL;struct ListNode* cur=head;head=NULL;while(cur){     if(cur->val==val)    { struct ListNode* del=cur; cur=cur->next; free(del); del=NULL;    }    else    { //尾插 if(tail==NULL) {     head=tail=cur; } else {    tail->next=cur;    tail=tail->next; }  cur=cur->next;    }}if(tail!=NULL)   tail->next=NULL;return head;}

思路三：

在思路二的基础上加一个哨兵位的头结点，哨兵位的头结点就是不存储有效数据。

代码如下： 

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* tail=NULL;struct ListNode* cur=head;  //哨兵位的头结点 head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); tail->next=NULL;while(cur){     if(cur->val==val)    { struct ListNode* del=cur; cur=cur->next; free(del); del=NULL;    }    else    { //尾插    tail->next=cur;    tail=tail->next; cur=cur->next;    }}   tail->next=NULL;struct ListNode* del=head;head=head->next;free(del);return head;}

如果在写的过程中有错可以放到vs下去调试，调试代码如下：

#include struct ListNode{    int val;    struct ListNode* next;};struct ListNode* removeElements(struct ListNode* head, int val) {    struct ListNode* tail = NULL;    struct ListNode* cur = head;    //哨兵位的头结点    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));    tail->next = NULL;    while (cur)    { if (cur->val == val) {     struct ListNode* del = cur;     cur = cur->next;     free(del);     del = NULL; } else {     //尾插     tail->next = cur;     tail = tail->next;     cur = cur->next; }    }    tail->next = NULL;    struct ListNode* del = head;    head = head->next;    free(del);    return head;}int main(){    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));    assert(n1);    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));    assert(n2);    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));    assert(n3);    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));    assert(n4);    n1->val = 7;    n2->val = 7;    n3->val = 7;    n4->val = 7;    n1->next = n2;    n2->next = n3;    n3->next = n4;    n4->next = NULL;    struct ListNode* head = removeElements(n1, 7);    return 0;}

好了，今天就分享到这里。