LC 203. 移除链表元素

题目描述

这是 LeetCode 上的 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

输出：[]

提示：

• 列表中的节点在范围 $[0, 10^4]$ 内
• $1 <= Node.val <= 50$
• $0 <= k <= 50$

---

递归

一个直观的做法是：写一个递归函数来将某个值为 val 的节点从链表中移除。

由于是单链表，无法通过某个节点直接找到「前一个节点」，因此为了方便，我们可以为递归函数多设置一个入参，代表「前一个节点」。

Java 代码：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        dfs(dummy, dummy.next, val);
        return dummy.next;
    }
    void dfs(ListNode prev, ListNode root, int val) {
        if (root == null) return ;
        if (root.val == val) prev.next = root.next;    
        else prev = root;
        dfs(prev, prev.next, val);
    }
}

C++ 代码：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        dfs(dummy, head, val);
        return dummy->next;
    }
    void dfs(ListNode* prev, ListNode* root, int val) {
        if (!root) return;
        if (root->val == val) prev->next = root->next;
        else prev = root;
        dfs(prev, root->next, val);
    }
};

Python 代码：

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head
        self.dfs(dummy, dummy.next, val)
        return dummy.next
    def dfs(self, prev, root, val):
        if not root:
            return 
        if root.val == val:
            prev.next = root.next
        else:
            prev = root
        self.dfs(prev, prev.next, val)

• 时间复杂度：$O(n)$
• 空间复杂度：忽略递归带来的额外空间开销。复杂度为 $O(1)$

---

迭代

同理，我们可以使用「迭代」方式来实现，而迭代有 while 和 for 两种写法。

Java 代码（for）：

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

Java 代码（while）：

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

C++ 代码：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* tmp = dummy->next;
        ListNode* prev = dummy;
        while (tmp != nullptr) {
            if (tmp->val == val) prev->next = tmp->next;
            else  prev = tmp;
            tmp = tmp->next;
        }
        return dummy->next;
    }
};

Python 代码：

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head
        tmp, prev = dummy.next, dummy
        while tmp:
            if tmp.val == val:
                prev.next = tmp.next
            else:
                prev = tmp
            tmp = tmp.next
        return dummy.next

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.203 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。