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

Iterative solution with dummy, O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head != null && head.next != null){
            if (head.next.val == val){
                head.next = head.next.next;
            }else{
                head = head.next;
            }
        }
        return dummy.next;
    }
}

Iterative solution without dummy, O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
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;
    }
}

Recursive solution, O(n) time O(n) space

1
2
3
4
5
6
7
public class Solution {
    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;
    }
}