leedcode.203移除链表元素

系列文章目录

初识单链表

文章目录

给你一个链表的头节点 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都向后移，
这样遍历完之后就可以删完。

structListNode*removeElements(structListNode* head,int val){structListNode* prev =NULL;structListNode* 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

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

structListNode*removeElements(structListNode* head,int val){structListNode* prev =NULL;structListNode* 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的尾插。

代码如下：

structListNode*removeElements(structListNode* head,int val){structListNode* tail =NULL;structListNode* cur = head;
    head =NULL;while(cur){if(cur->val == val){structListNode* 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;}

今天的分享就到这里辣。