LeetCode 203 移除链表元素 | Java 刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

移除链表元素

给你一个链表的头节点 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 <= k <= 50

思路分析

像这样一道简单的链表题，更多考察的是你的编程能力，而不是算法能力，本文将给出四种解法，普通解法，使用虚拟头结点的优化解法，递归解法，还有一个改变链表的万能写法。

代码展示

解法一：普通解法，时间复杂度是 ${O(n)}$ ，空间复杂度也是 ${O(1)}$ 。

    public ListNode removeElements(ListNode head, int val) {
        //方法一
        //如果头结点一开始就是目标
        while (head != null && head.val == val){
            head = head.next;
        }
        if (head == null){
            return null;
        }
        ListNode prev = head;
        while (prev.next != null){
            if (prev.next.val == val){
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return head;
    }
复制代码

解法二：使用虚拟头结点优化解法，时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(1)}$ 。

      public ListNode removeElements(ListNode head, int val) { 
				ListNode dumpHeader = new ListNode(val+1,head);
        ListNode prev = dumpHeader;
        while (prev.next != null){
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }

        return dumpHeader.next;
      }
复制代码

解法三：递归解法

		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;
        }
     }
复制代码