LeetCode203.移除链表元素🌟🌟🌟🌟🌟简单

算法系统课免费

问题描述

给你一个链表的头节点 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
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

思路讲解

代码实现

Java

/**
 * 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) {
        // 删除头节点
        while(head != null && head.val == val){
            head = head.next;
        }

        if(head == null){
            return head;
        }

        ListNode cur = head.next;
        ListNode pre = head;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next; 
            }else{
                pre = cur;
            }
            cur = cur.next;
        }

        return head;
    }
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        # 删除头节点
        while(head != None and head.val == val):
            head = head.next

        if(head == None):
            return head

        cur = head.next
        pre = head
        while(cur != None):
            if(cur.val == val):
                pre.next = cur.next 
            else:
                pre = cur
            cur = cur.next

        return head

C++

/**
 * 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) {
        // 删除头节点
        while(head != nullptr && head->val == val){
            head = head->next;
        }

        if(head == nullptr){
            return head;
        }

        ListNode* cur = head->next;
        ListNode* pre = head;
        while(cur != nullptr){
            if(cur->val == val){
                pre->next = cur->next; 
            }else{
                pre = cur;
            }
            cur = cur->next;
        }

        return head;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    // 删除头节点
    for head != nil && head.Val == val {
        head = head.Next
    }

    if head == nil {
        return head
    }

    cur := head.Next
    pre := head
    for cur != nil {
        if cur.Val == val {
            pre.Next = cur.Next
        } else {
            pre = cur
        }
        cur = cur.Next
    }

    return head
}

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: # 有虚拟头节点 def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummyHead = ListNode(-1, head) cur = dummyHead while cur.next: if cur.next.val == val: cur.next = cur.next.next else: cur = cur.next return dummyHead.next #递归法 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: if not head: return head.next = self.removeElements(head.next, val) return head.next if head.val == val else head

/** * 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; } * } */ // 【迭代法】 // 时间复杂度：O(n)，遍历比较 // 空间复杂度：O(1)，只开辟两个ListNode，即两个指针 class Solution { public ListNode removeElements(ListNode head, int val) { while(head != null && head.val val) { //头节点与目标val值判断 head = head.next; } if(head null) { //必须放在头节点值判断之后 return head; } //头节点不可动 if(head.next != null) { //虽然头节点不为空，但其后继有可能为空 ListNode sub = head.next; //后继 ListNode pre = head; //前驱 while(sub != null) { //直到链表所有元素值判断完成 if(pre.next.val val) { //等价于(sub.val val) pre.next = sub.next; //必须先改变前驱的指向，否则丢失后面的链表 } else { pre = sub; } sub = pre.next; } } return head; //返回头节点，即整个链表 } } // 【递归法】学习解题思路 // 时间复杂度：O(n)，遍历比较 // 空间复杂度：O(n) // class Solution { // public ListNode removeElements(ListNode head, int val) { // //函数目的：head.val与val值比较，若相同则返回head = head.next.next // //递归结束条件 // if(head null) { // return head; // } // //关系式 // head.next = removeElements(head.next, val); // return head = head.val val ? head.next : head; // } // }

class Solution { public ListNode removeElements(ListNode head, int val) { // 删除头节点 while (head != null && head.val == val) { head = head.next; } // 链表为空（头节点是否为空） if (head == null) { return head; } ListNode cur = head.next; ListNode pre = head; while (cur != null) { if (cur.val == val) { pre.next = cur.next; } else { pre = cur; } cur = cur.next; } return head; } }

class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; ListNode cur = head; while (cur != null){ if(cur.val == val){ pre.next = cur.next; }else pre = pre.next; cur = cur.next; } return dummy.next; } }

发表回复取消回复

后才能评论

我来吃饭啦永久会员 2024年6月17日下午2:49

Yuki 永久会员 2024年1月27日上午11:28

打卡
https://leetcode.cn/problems/remove-linked-list-elements/solutions/2621486/203-yi-chu-lian-biao-yuan-su-by-yukislab-qteh

登录以回复

uu 永久会员 2023年9月19日上午11:53

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

分情况（删除头结点，空节点和非头节点），不分情况（虚拟头节点）

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

自己的模板，用虚拟头节点可以避免删除头节点的问题

帅气的冬瓜普通 2023年6月26日下午5:25

打卡

登录以回复

问题描述

思路讲解

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(6)

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复