Remove Linked List Elements

In this exercise, we need to remove the nodes with value val from a linked list.

Algorithm

We handle 3 cases in the recursion:

1. head is null, return null
2. head.val is val, return removeElements(head.next)
3. head.val is not val, return head -> removeElements(head.next)

Code

From these 3 cases, we obtain the code below:

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    ListNode next = removeElements(head.next, val);
    if (head.val == val) {
        return next;
    }
    head.next = next;
    return head;
}

This time, let’s include the non recursive version. This is done by updating the input and skipping the elements with value val:

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

Time and Space Complexity

Both implementations are O(n) in time. In space the first implementation is O(n), and the second one is O(1).