# LeetCode Remove Linked List Elements: Iterative vs Recursive

## Overview

LeetCode Remove Linked List Elements: 4 different implementations are given as well as details of comparing Iterative vs Recursive methods.

## LeetCode Remove Linked List Elements

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

## LeetCode Remove Linked List Elements: Iterative vs Recursive

There is no fancy algorithm involved here but we do have smarter implementation and less smart implementations. The basic idea is simple, check each node, if it is the one that needs to be deleted, delete it. There are two ways to delete it:

1. Maintain a the reference/pointer to the previous node of the deleted one, and set the previous not next pointer to current node’s next pointer
2. Directly set the current node to the value of its next and set the current node’s next its next’s next, as shown in this related similar problem: LeetCode Delete Node in a Linked List: O(1) Time and Space. This one is preferred as for myself.

Also three additional things worth noting:

1. Recursive implementation is elegant but cost O(N) space
2. Do not forget the special case that all of the elements need to be deleted and thus the linked list becomes an empty one
3. You might want to check this similar problem but in a array context for further reference: LeetCode Remove Element: Swap with Two Pointers

The following three iterative implementation could be accepted by LeetCode OJ to pass this Remove Linked List Elements problem, and the last version (version 3) of these three is the best elegant implementation:

This is version 1:

This is version 2 as similar to this problem: LeetCode Delete Node in a Linked List: O(1) Time and Space:

This is version 3:

The following recursive implementation gives the shortest code but cost O(N) space, but I still think it is quite clever if we can come up with such recursive version, the following code could be accepted by LeetCode OJ to pass this Remove Linked List Elements problem as well:

## Summary

LeetCode Remove Linked List Elements: 4 different implementations are given as well as details of comparing Iterative vs Recursive methods.

Written on July 27, 2015