【LeetCode】203. 移除链表元素

in programming •  3 months ago 

1 题目描述

203. 移除链表元素要求给定一个链表的头节点 head 和一个整数 val,任务是删除链表中所有满足 Node.val == val 的节点,并返回新的头节点。

2 解题思路

  1. 使用虚拟头节点:为了简化边界情况(例如当头节点需要被删除时),我们可以创建一个虚拟头节点 dummy,它指向原链表的头节点。这样可以避免额外的条件判断。
  2. 遍历链表:通过一个指针 cur 遍历链表,每次检查 cur.next 节点是否需要被删除。
  3. 删除节点:如果 cur.next 的值等于 val,则将 cur.next 指向下一个节点(即跳过当前节点);否则,将 cur 向前移动一位。
  4. 返回结果:最后返回 dummy.next 即为新的链表头节点。

3 Java 代码实现

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 创建虚拟头节点
        ListNode dummy = new ListNode(-1, head);
        // 初始化 cur 指针指向虚拟头节点
        ListNode cur = dummy;
        
        // 遍历链表
        while (cur.next != null) {
            // 如果找到值为 val 的节点,则删除该节点
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                // 否则,继续向前移动
                cur = cur.next;
            }
        }
        
        // 返回新链表的头节点
        return dummy.next;
    }
}```

- **时间复杂度:** O(n),其中 n 是链表中的节点数量。我们需要遍历整个链表一次。
- **空间复杂度:** O(1),只需要常量级额外空间。

# 4 注意事项
- **哑节点**:引入哑节点 `dummy` 以简化代码逻辑,避免处理头节点的特殊情况。
- **遍历链表**:使用 `cur` 指针来遍历链表,处理每一个节点。
- **删除节点**:当遇到值为 `val` 的节点时,直接跳过该节点,不改变 `cur` 指针的位置。
- **返回新头节点**:返回 `dummy.next` 作为新的链表头节点。
Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!