203.移除链表元素

浅浅的花香味﹌ 2024-03-17 20:21 30阅读 0赞

#### 203.移除链表元素 ####

*  题目背景
 *  重要思路
 *  具体代码
 *   *  添加虚节点方式
     *  不添加虚拟节点方式
     *  不添加虚拟节点and pre Node方式

## 题目背景 ##

[力扣入口-203. 移除链表元素  
][-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 <= val <= 50

## 重要思路 ##

关键点就在头节点上，如果为null，则返回null。如果不是则需要避免头节点的值就是目标值，那么头节点则会被删除。

方法一是添加一个新的虚节点，方法二是更换头节点。

方法三是用两次next的方法来代替pre和cur，不过要注意这里需要修改成while循环。

## 具体代码 ##

### 添加虚节点方式 ###

/**
     * 添加虚节点方式
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        
        if(head == null){
        
            return head;
        }
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur != null){
        
            if(cur.val == val){
        
                pre.next = cur.next;
            }else{
        
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }

### 不添加虚拟节点方式 ###

/**
     * 不添加虚拟节点方式
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val){
        
        while(head != null && head.val == val){
        
            head = head.next;
        }
        // 已经为null，提前退出
        if (head == null) {
        
            return head;
        }
        // 已确定当前head.val != val
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {
        
            if (cur.val == val) {
        
                pre.next = cur.next;
            } else {
        
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

### 不添加虚拟节点and pre Node方式 ###

public ListNode removeElements(ListNode head, int val) {
        
        while(head != null && head.val == val){
        
            head = head.next;
        }
        ListNode curr = head;
        while(curr!=null) {
        
            while (curr.next != null && curr.next.val == val) {
        
                curr.next = curr.next.next;
            }
            curr = curr.next;
        }
        return head;
    }

**参考资料**：[203.移除链表元素][203.]

[-203. _]: https://leetcode.cn/problems/remove-linked-list-elements/
[203.]: https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC