Leetcode 203 - Removed Linked List Elements

Problem Statement

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def removeElements(self, head, val):
dummy = head
prev = head
while head and head.val == val:
head = head.next
dummy = head
while head:
if head.val == val:
prev.next = head.next
else:
prev = head
head = head.next
return dummy

Time: O(N)
Space: O(1)

Explanation

The first trick test case is 6->6->6->6. In this case, we keep advancing the dummy node until either head is no longer a node and head.val != val. Then the regular case is: 1->2->6->3->4->5->6. The trick is that when the head.val == val, we are not going to update the previous value to the current head value.