Remove Linked List Elements

Linked lists are fundamental data structures widely used in programming and algorithmic problem-solving. One common task when working with linked lists is removing specific elements based on a given criterion.

Problem Statement:

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

In this article, we will delve into the problem of removing elements from a linked list that match a target value. We will explore different approaches to solve this problem, each with its own advantages and considerations. We will examine the code implementation in JavaScript and discuss its time and space complexity.

Approach 1: Iterative solution

So the basic idea is to traverse the linked list and once we find a node that matches the target value, we need to adjust the next pointer of the previous node to skip the current node and directly connect to the next node.

1. Start with a pointer at the head of the linked list.

2. Traverse the linked list, checking each node’s value.

3. If the current node’s value matches the target value, skip the node by adjusting the pointers.

4. Move the pointer to the next node.

5. Repeat steps 3 and 4 until the end of the list is reached.

// ES6 Arrow Function
const removeElements = (head, val) => {
    if(head === null) return head;

    let dummy = new ListNode(0);
    dummy.next = head;

    let current = dummy;

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

    return dummy.next;
}

Time complexity: O(N), where N is the number of nodes in the linked list.

In the worst-case scenario, we have to visit all the nodes once so the time complexity is linear.

Space Complexity: O(1)

As we only require a few pointers for traversal and adjustment, regardless of the size of the linked list. The space complexity is constant.

Approach 2: Recursive

1. So we start with a base case check: if the head is null (indicating an empty list), there's nothing to remove, so it returns null immediately.

2. If the head is not null, it means there are nodes in the linked list. The code proceeds to make a recursive call on the next node. This recursive call is crucial to traverse through the entire linked list, starting from the next node, and remove the elements with the target value recursively.

3. After the recursive call returns, the code checks if the value of the current node is equal to the target value. If they match, it means the current node needs to be removed.

4. If the current node’s value matches the target value, the code simply skips the current node. By doing so, the previous node (which made the recursive call) will now be connected to the next node of the current node, bypassing the current node.

5. If the current node’s value does not match the target value, it means the current node is not to be removed. In this case, the code simply returns head, ensuring that the current node is kept in the list.

6. Finally, when the recursive calls are complete and the function reaches the initial call, the modified linked list (with the target value removed) is returned as the result.

// ES6 Arrow Function
const removeElements = (head, val) => {
    // base case
    if(head === null) return null;

    // recursive call on the next node
    head.next = removeElements(head.next, val);

    // check if the current node's value matches the target value
    if(head.val === val) return head.next;

    return head;
}

Time complexity: O(N)

The recursive function needs to traverse all the nodes of the linked list once, similar to the iterative approach.

Space Complexity: O(N)

In the worst case, if all nodes have the target value, the recursive function will be called n times before reaching the base case. Therefore, the space complexity is proportional to the length of the linked list.

And there you have it guys! We’ve explored two different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 203