RemoveLinkedListElements [source code]

public class RemoveLinkedListElements {
static
/******************************************************************************/
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode prev = head, res = head;
        while (head != null) {
            if (head.val == val) {
                if (head == prev) {
                    head = head.next;
                    prev.next = null;
                    res = head;
                    prev = head;
                } else {
                    prev.next = head.next;
                    head.next = null;
                    head = prev.next;
                }
            } else {
                prev = head;
                head = head.next;
            }
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RemoveLinkedListElements.Solution tester = new RemoveLinkedListElements.Solution();
        int[][] inputs = new int[][]{
            {1,2,6,3,4,5,6}, {6},
            {1}, {1},
            {1,1}, {1},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            Printer.separator ();
            System.out.println("test case " + (i / 2 + 1));
            ListNode node = ListNode.buildListNode(inputs[2 * i]);
            System.out.println("before: ");
            ListNode.serialize (node);
            int k = inputs[1 + 2 * i][0];
            System.out.println("after: ");
            ListNode.serialize (tester.removeElements(node, k));
        }
    }
}

Delete head.next(跳子思路) 的致命缺陷: 无法处理consecutive duplicates

这个方法看起来聪明, 不过这个跳子的方法其实更多的就是适用于那一个题目而已, 因为那个题目给的条件是你没有整个 list 的 head, 所以只能用这种跳子的思路; 这种跳子的思路如果碰到连续的两个 duplicate, 只能删除右边的一个, 左边的一个就完全没有办法;
这个题目我们有整个 list 的 head, 所以可以用更强力一点的办法;

绕过这个弯之后整个问题就简单了, 想好if else里面你写哪几个 if, 也就是考虑哪几个 decision 就行了; 这里先判断 val 是否相等. 如果相等, 还要判断当前 head 是否是 list 的头. 基本逻辑还是很简单的, 最后的速度是2ms (10%), 一般化, 可能跟题目比较老有一定关系;

这个是 submission 最优解 1(63):

public class Solution {  
    public ListNode removeElements(ListNode head, int val) {  
        if(head == null) return null;  
        ListNode currentNode = head;  
        while(currentNode.next!=null){  
            if(currentNode.next.val == val) currentNode.next = currentNode.next.next;  
            else currentNode = currentNode.next;  
        }  
        return (head.val == val)?head.next:head;  
    }  
}

这个思路我其实是想到了的, 不过最后没有用这个思路来写, 而是用相对复杂一些的一个思路来写; 我的思路里面, 用 prev 来保存 parent, 以完成删除操作; 这里的做法更简单, 我们不判断 head 本身, 而判断head.next, 这样, 如果某一个 iteration 我们知道了 val 相等, 我们同时也拥有the pointer to the node with the matching value;

判断null 还是判断 leaf

这个在 graph 问题的时候就总结过一次. 应该说, 这个问题在 graph 问题里面都不是显得那么重要, 虽然两种思路最后得到的代码的难度会不一样; 但是在 LinkedList 问题里面, 这个就比较重要, 因为 LinkedList 问题很多时候whether you have the access to the parent link/pointer往往就是关键. 这个题目, 如果判断 leaf 而不是 Null, 最后写出来的代码难度简化很多;

突然想到这个题目更加简单的一个思路, 应该是直接不做 InPlace 就行了, 重新建一个 list, 然后一个一个 append 简单的多;

这个题目一个难点在于你怎么处理最开始的 hit, 因为后面的 hit 都是可以直接统一处理的, 但是最开头的这个, 不太好处理;
这里这个算法的做法是, 直接无视最左, 然后最后再来处理它.

discussion 里面对于最左的处理还有其他的思路, 比较好的是: dummy head的做法;

public ListNode removeElements(ListNode head, int val) {  
    ListNode dummy = new ListNode(0);  
    dummy.next = head;  
    ListNode cur = dummy;  

    while(cur.next != null) {  
        if(cur.next.val == val) {  
            cur.next = cur.next.next;  
        }  
        else  
            cur = cur.next;  
    }  
    return dummy.next;  
}

注意这个算法同时还做到了不使用 prev, 因为他判断的是 leaf;

Dummy Head

目前还不知道怎么总结 dummy 的用法, 这里的用法有人认为是为了avoid edge cases. 我来看的话, 我认为也可以是让最左成为跟 list internal 的 node 一样的性质; 有点像一种 normalization 的手段;

这个就是为了避免 dummy, 就直接先把从 head 开始的 hit 全部处理掉:

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

我一开始也是有这个想法, 不过后来还是使用了我现在的这个思路; 我自己现在的这个思路其实就是在普通的处理里面加一个(通过指针比较)对最左的判断, 然后单独给一个 branch 处理一下就行了;

这个是 discussion 里面一个 recursion 做法:

public ListNode removeElements(ListNode head, int val) {  
        if (head == null) return null;  
        head.next = removeElements(head.next, val);  
        return head.val == val ? head.next : head;  
}

很简洁; 比拿着两个小指针自己比划要简练很多; 而且他这个其实也是 InPlace 的; 如果还是在上426的课程, 估计这个算法很容易想到;
当然 recursion 的一个问题是, 这个 recursion 并不是tail recursion; 所以如果一个 list 很长, 这个可能会 overflow;

Problem Description

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:116.6K
Total Submissions:362.6K
Contributor: LeetCode
Related Topics
linked list
Similar Questions
Remove Element Delete Node in a Linked List