脚撕LeetCode(203)Easy

题目地址：https://leetcode-cn.com/problems/remove-linked-list-elements/

给你一个链表的头节点 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 https://leetcode-cn.com/problems/remove-linked-list-elements/

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

第一次爆破法和官方方法出奇的一致，感觉这道题应该是简单到无可避免了

一、爆破法：

思路很简单，先创建一个头节点（反正最后都要删除的，这么做也省去了头节点的判断），他的next是传过来的head

然后双指针法，一个指向当前，一个指向next，然后不断的循环，条件是next部位null

循环体内如果判断next的val = 传来的val则this指向next的next，否则this =next，然后统一步骤next指向next的next，循环结束，返回我们创建的头节点的next

执行结果如下：

66 / 66 个通过测试用例

状态：通过

执行用时: 1 ms

内存消耗: 39.3 MB

public static ListNode removeElementsMe(ListNode head, int val) {
    ListNode newHead = new ListNode(-1, head);
    ListNode thisNode = newHead;
    ListNode nextNode = head;
    while (null != nextNode) {
        if (nextNode.val == val) {
            thisNode.next = nextNode.next;
        } else {
            thisNode = nextNode;
        }
        nextNode = nextNode.next;
    }
    return newHead.next;
}

评论区似乎找不到时间和空间更好的办法，就贴一个看起来没想到的思路好了

二、递归法

每个节点递归判断，不需要双指针法，但是时间和空间上反而比我的方法给评分低

执行结果：

66 / 66 个通过测试用例

状态：通过

执行用时: 1 ms

内存消耗: 39.6 MB

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;
    }
}

总结，可能是因为自己递归写的少，所以递归的思路并没有想到，但是虚拟头节点这个办法感觉很不错，可以躲避头节点的判断尴尬，总的来说算是有收获的