## Problem

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

Example:

```
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
```

## Thought Process

- the regular case is simple.

e.g. to delete 6 below, we can use a node(delnode) to store 6’s next node

```
2->6->3
```

then 2’s next points to delnode’s next node, then 6’s next points to None

- The tricky part is the edge case:
- if the deleted node is None, then return None
- if the deleted node is head, then delnode = head, delnode.next = head.next, then remove head
- it’s possible that after nth deletion, the new head might still be the target node to be removed. Here we need a loop
- also after deleting nodes, it’s possible that the linked list is empty, then return None

## White Board

Below is the white board:

## Code

```
class listNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def removeElements(self, head, val):
if head is None:
return head
while(head is not None and head.val == val):
delNode = head
head = delNode.next
delNode = None
if head is None:
return head
curr = head
while(curr.next is not None):
if (curr.next.val == val):
delNode = curr.next
curr.next = delNode.next
delNode = None
else:
curr = curr.next
return head
```

## Result1

## Complexity

- Time complexity is O(n)

## Optimization

There are just way too many edge case evaluations in the above solution. One good solution is to introduce a dummy head whose next points to head

```
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def removeElement(self, head, val):
dummyHead = ListNode(-1)
dummyHead.next = head
curr = dummyHead
while curr.next is not None:
if curr.next.val == val:
delNode = curr.next
curr.next = delNode.next
delNode.next = None
else:
curr = curr.next
return dummyHead.next
```

```
```

The Time complexity is also O(n), but there are much less operations