【作业5】链表专题：用递归解决LeetCode203.移除链表元素-跟着帅地玩副业，开拓第二曲线PlayOffer

幽小皮永久会员 2024年4月1日下午6:38

class Solution {
//移除Node.val val的节点
public ListNode removeElements(ListNode head, int val) {
while(head != null && head.val val){
head = head.next;
}
if(head null){
return head;
}
ListNode pre = head;
ListNode cur = head.next;
if(cur null){
return head;
}else if(cur.val val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = pre.next;
//修改pre并递归
pre = removeElements(pre, val);
return head;
}
}
“`java
空间时间复杂度都为O(n)

0 赞同 0 条回复

少年不识流川枫永久会员 2024年2月27日下午1:52

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //递归调用 1.整体removeElements 2.结束条件 3.等价关系式

        //2.结束条件
        if(head == null){
            return head;
        }
        //3.等价关系式,缩小范围,去除头节点并判断满足条件不？
                            //满足    不满足
        if(head.val == val){
            head = removeElements(head.next, val);
        }else{
            head.next = removeElements(head.next, val);
        }
        return head;
    }
}

第一行代码中的head = removeElements(head.next, val); 是将当前节点的下一个节点作为新的头节点，并传入removeElements函数进行递归删除操作。

第二行代码中的head.next = removeElements(head.next, val); 是将当前节点的下一个节点重新连接到删除操作后的链表，并传入removeElements函数进行递归删除操作。
时间复杂度，空间复杂度O(n)

1 赞同 0 条回复

泡芙永久会员 2023年9月1日下午2:45

递归
– Time：O(n)，遍历所有节点
– Space ：O(n)，递归调用栈深度为n

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 递归终止条件
        if (head == null) {
            return null;
        }
        // 关系式
        head.next = removeElements(head.next, val);
        // if (head.val == val) {
        //     return head.next;
        // } else {
        //     return head;
        // }
        return head.val == val ? head.next : head;
    }
}

1 赞同 0 条回复

八点上线永久会员 2023年8月31日下午4:30

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head <span class="text-highlighted-inline" style="background-color: #fffd38;"> null){
            return null;
        }
        if(head.val </span> val){
            return removeElements(head.next,val);
        }
        head.next = removeElements(head.next,val);
        return head;
    }
}

打卡

0 赞同 0 条回复

AD钙奶普通 2023年8月30日上午12:08

打卡

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return head;

        if(head.val == val) head = removeElements(head.next,val);
        else head.next = removeElements(head.next,val);
        return head;
    }
}

0 赞同 0 条回复

Thaddeus 永久会员 2023年8月28日下午4:18

打卡

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr) return nullptr;

        head->next = removeElements(head->next, val);
        if(head->val == val) return head->next;
        else return head;
    }
};

0 赞同 0 条回复

阿尚普通 2023年8月17日上午10:33

class Solution {
    public ListNode removeElements(ListNode head, int val) {
       if(head==null)
           return null;
        head.next=removeElements(head.next,val);
        if(head.val==val){
            return head.next;
        }else{
            return head;
        }
    }
}
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

纸飞机永久会员 2023年8月8日下午3:04

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
       // 这个函数的功能是删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
       if(!head)
       {
           head=nullptr;
       }
       else if(!head->next)
       {
           if(head->val == val)
           {
               head = nullptr;
           }
           else
           {
               head=  head;
           }
       }
       else
       {
           if(head->val != val)
           {
               head->next = removeElements(head->next,val);
           }
           else
           {
               head = head ->next;
               head = removeElements(head,val);
           }

       }
       return head;
    }
};

0 赞同 0 条回复

𬍤永久会员 2023年7月27日下午4:37

class Solution {
    public ListNode removeElements(ListNode head, int val) {

        //递归做法
        if(head == null){
            return null;
        }

        head.next = removeElements(head.next,val);

        if(head.val == val){
            return head.next;
        }else{
            return head;
        }
    }
}

时间复杂度O(n)，空间复杂度O(n)

0 赞同 0 条回复

3_🔥 永久会员 2023年7月9日下午9:52

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //递归写法 1.找出口
        if(head == null)  return null;
        //2.缩小范围
        if(head.val == val) head = removeElements(head.next,val);
        else head.next = removeElements(head.next,val);
        return head;
    }
}

时间复杂度：O(n)，n为链表的长度，需要遍历整个链表。

空间复杂度：O(n)，n为递归栈的深度，最坏情况下链表中所有节点都需要被删除，递归栈的深度为n

0 赞同 0 条回复

Mr.肖永久会员 2023年7月6日下午8:39

打卡：

class Solution {
    public ListNode removeElements(ListNode head, int val) {

        return  head = removeElements2(head,val);


    }

    //递归算法
    //删除以node为头节点的链表中的val节点，返回链表的头节点
    private ListNode removeElements2(ListNode node,int val){

        if(node==null)
            return null;
        if(node.val == val){
            return removeElements2(node.next,val);
        }
        node.next= removeElements2(node.next,val);
        return node;
    }
}

0 赞同 0 条回复

KEV 永久会员 2023年6月6日下午3:40

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==nullptr){
            return nullptr;
        }
        // 算出后续
        head->next=removeElements(head->next,val);
        // 判断当前
        if(head->val==val){
            return head->next;
        }else{
            return head;
        }

    }
};

0 赞同 0 条回复

LicodeCO.LTDao 普通 2023年5月20日下午3:52

function removeElements(head: ListNode | null, val: number): ListNode | null {
    // 空链表
    if(head == null) {
        return head
    }
    // 缩小问题规模
    head.next = removeElements(head.next, val)

    return head.val === val ? head.next : head
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年5月16日下午7:31

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //结束条件
        if(head == null){
            return null;
        }

        //缩小规模----f(n-1)
        //把子串中的val删除完了之后，给我返回子串的head
        ListNode subListHead = removeElements(head.next,val);   //子串的head

        //自己做一些事
        //把自己接到子串上
        head.next = subListHead;

        //看看自己是否要被删除
        if(head.val == val){
            return head.next;
        }else{
            return head;
        }
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年4月24日下午9:20

//时间复杂度和空间复杂度都是O(n)
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null)
            return head;
        if(head.val == val){
            head = removeElements(head.next, val);
        }else{
            head.next = removeElements(head.next, val);
        }
        return head;
    }
}

0 赞同 0 条回复

Only You!(^-^(^-^)) 永久会员 2023年4月20日下午3:56

//递归实现
    /*对于给定的链表，首先对除了头节点 head以外的节点进行删除操作，
    * 然后判断 head的节点值是否等于给定的 val。
    * 如果 head的节点值等于 val，则 head需要被删除，因此删除操作后的头节点为 head.next；
    * 如果 head的节点值不等于 val，则 head保留，因此删除操作后的头节点还是 head。
    */
    //时间复杂度：O(n) 空间复杂度：O(n)
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements(head.next,val);
        if (head.val == val) {
            return head.next;
        }else {
            return head;
        }
    }

0 赞同 0 条回复

庄重普通 2023年4月17日下午10:37

class Solution {
public:
    // 功能：返回删除后的头节点 // 1,2,3,4,5,6 -》1,2,3,4,5
    ListNode* removeElements(ListNode* head, int val) {
        // 结束条件
        if(head == nullptr) return head;
        // 关系式
        ListNode *p = removeElements(head->next, val); // 2,3,4,5
        head->next = p;
        if(head->val == val) { // 头节点需要被删除
            return head->next;
        }else{  // 头节点不需要被删除
            return head;
        }
    }
};
// 时间复杂度O(n);
// 空间复杂度O(n);

0 赞同 0 条回复

小趴菜永久会员 2023年4月17日上午3:35

时间o（n），空间o（n）
class Solution {
//函数的功能是删掉val的节点
public ListNode removeElements(ListNode head, int val) {
//递归结束条件，如果不为空则一直递归调用下去
if(head null){
return head;
}
head.next = removeElements(head.next,val);
//删除的方法，遇到是目标值那就直接删除，所以返回的是next，如果不是目标值那就正常出栈
return head.val val?head.next:head;
}
}

0 赞同 0 条回复

小肸永久会员 2023年4月14日下午7:29

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        //removeElements()返回已经移除val值节点的子链表的头节点
        head.next = removeElements(head.next, val);//不断入栈
        //如果头节点的值等于val，就返回头节点的下一个节点作为头节点
        return head.val == val ? head.next : head;//不断出栈
    }
}

0 赞同 0 条回复

菜心永久会员 2023年4月14日上午10:19

时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return head;
        }
        head.next = removeElements(head.next, val);
        if(head.val == val){
            return head.next;
        }else{
            return head;
        }

    }
}

0 赞同 0 条回复

Bryce 普通 2023年4月12日下午11:49

go语言递归解法,时间复杂度O(n),空间复杂度O(n)

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }
    head.Next = removeElements(head.Next, val)
    if head.Val == val {
        return head.Next
    }
    return head
}

0 赞同 0 条回复

Violet 永久会员 2023年4月12日下午9:47

一

class Solution {
    public ListNode removeElements(ListNode head, int val) {
         if (head == null) return null;
         head.next = removeElements(head.next, val);
         if (head.val == val) {
             return head.next;
         } else {
             return head;
         }

    }
}

0 赞同 0 条回复

秊永久会员 2023年4月12日上午8:40

时间: $O(n)$
空间: $O(1)$

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode header = new ListNode(0, head); 
        reversal(header, val);
        return header.next;
    }

    private void reversal(ListNode cur, int val) {
        if (cur.next == null) return;

        if (cur.next.val == val) {
            cur.next = cur.next.next;
            reversal(cur, val);
        } else {
            reversal(cur.next, val);
        }

    }
}

0 赞同 0 条回复

是梦终空永久会员 2023年4月10日下午7:51

时间复杂度: O(n)

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null)    return head;
        head.next = removeElements(head.next,val);  //递归
        if(head.val == val){
            return head.next;
        }
        return head;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年4月10日下午2:24

时间复杂度：O(n)，n为链表的长度，需要遍历整个链表。

空间复杂度：O(n)，n为递归栈的深度，最坏情况下链表中所有节点都需要被删除，递归栈的深度为n

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
         }
        return f(head,val);
    }
    //定义方法
    public static ListNode f(ListNode head,int val){
     //结束条件
     if(head==null){
        return head;
     }
     if(head.val!=val) head.next=f(head.next,val);//如果不相等，就继续递归直到相等或者为空
     else return f(head.next,val); //如果相等，就返回下一个节点
     return head;
    }
}

0 赞同 0 条回复

Everglow 永久会员 2023年4月10日上午10:12

时间复杂度O(n)

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return null;
        }
        if(head.val != val) {
            head.next = removeElements(head.next, val);
            return head;
        } else {
            return removeElements(head.next, val);
        }
    }
}

0 赞同 0 条回复

易水寒永久会员 2023年4月9日下午9:48

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return head;
        }
        if(head.val == val) {
            return removeElements(head.next, val);
        }
        head.next = removeElements(head.next, val);
        return head;
    }
}

时间O(n), 空间O(n)

1 赞同 0 条回复

C++小将永久会员 2023年4月9日下午7:59

作业五打卡

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr) {
            return head;
        }
        head->next = removeElements(head->next, val);
        if(head->val == val) {
            return head->next;
        }else {
            return head;
        }
    }
};

时间复杂度O(n),空间复杂度O(n)

0 赞同 2 条回复

shuaidi 永久会员 @ C++小将 2023年4月9日下午9:21

要求用递归，你这个方法不是递归。

登录以回复
C++小将永久会员 @ shuaidi 2023年4月11日下午3:52

已修改

登录以回复

【作业5】链表专题：用递归解决LeetCode203.移除链表元素

共以下 28 个回答

打卡

作业五打卡

# 回答此问题取消回复

【作业5】链表专题：用递归解决LeetCode203.移除链表元素

共以下 28 个回答

打卡

作业五打卡

# 回答此问题 取消回复

# 回答此问题取消回复