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:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
// version 1
public class Solution {
    public ListNode removeElements(ListNode head, int val) {

	ListNode p1 = new ListNode(0);
	p1.next = head;

	ListNode p2 = p1;
	ListNode p3 = head;

	while (p3 != null) {
		if (p3.val == val) {
			p2.next = p3.next;
			p3 = p3.next;
		} else {
			p2 = p3;
			p3 = p3.next;
		}
	}

	return p1.next;
    }
}

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
// version 2
public class Solution {

    public ListNode removeElements(ListNode head, int val) {

		ListNode p1 = new ListNode(0);
		p1.next = head;

		ListNode p2 = p1;
		ListNode p3 = head;

		while (p3 != null && p3.next != null) {
			if (p3.val == val) {
				p3.val = p3.next.val;
				p3.next = p3.next.next;
			} else {
				p2 = p3;
				p3 = p3.next;
			}
		}

		if (p3 != null && p3.val == val) {
			p2.next = null;
		}

		return p1.next;
    }
}

This is version 3:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
// version 3
public class Solution {

    public ListNode removeElements(ListNode head, int val) {

		ListNode p1 = new ListNode(0);
		p1.next = head;

		ListNode p2 = p1;

		while (p2 != null) {
			if (p2.next != null && p2.next.val == val) {
				p2.next = p2.next.next;
			} else {
				p2 = p2.next;
			}
		}

		return p1.next;
    }
}

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:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
	if (head == null) {
		return null;
	}

	if (head.val == val){
		head =
                removeElements(head.next, val);
	} else {
		head.next =
                removeElements(head.next, val);
	}

	return head;
    }
}

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