Problem

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

Example

Example 1:

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

Solution

The key to solve this problem is using a dummy node to track the head of the list.

Method 1 - Iterative and tracking next pointer

Code

Java
public ListNode removeElements(ListNode head, int val) {
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	ListNode p = dummy; // p is like previous pointer

	while (p.next != null) {
		if (p.next.val == val) {
			ListNode next = p.next;
			p.next = next.next;
		} else {
			p = p.next;
		}
	}

	return dummy.next;
}

Method 2 - Iterative and tracking Prev Pointer

Code

Java
public ListNode removeElements(ListNode head, int val) {
	ListNode dummy = new ListNode(-1);
	dummy.next = head;
	ListNode curr = head, prev = dummy;
	while (curr != null) {
		if (curr.val == val) {
			prev.next = curr.next;
		} else {
			prev = prev.next;
		}
		curr = curr.next;
	}
	return dummy.next;
}

Method 3 - Recursive

Code

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