leedcode.203移除链表元素

初识单链表

• 系列文章目录
• 方法一：该我删的我就删:tangerine:
• 方法二：不该删的我留下:peach:

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1

输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7

输出：[]

当遇到Node.val==val时，

为了将cur结点移除，cur的前一个结点prev应该存放cur的后一个结点的地址，free掉用删除的结点，并且cur向后移动一位。

当Node.val != val时,prev和cur都向后移，
这样遍历完之后就可以删完。

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

错辣！
我们看执行用例，7，7，7，7，
再创建一个1，7，7，7

看来是头删的问题，那就加个头删。

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)
        {
            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的尾插。

代码如下：

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);
        
    }
    else
    {
       //尾插
        if(tail == NULL)
        {
            head = tail = cur;
        }
        else
        {
            tail->next = cur;
            tail = tail->next;
        }
        cur = cur->next;
    }  
 }
    if(tail)
        tail->next = NULL;
    return head;
}

今天的分享就到这里辣。