DAY 97 - Removing Elements from a Linked List
Tags: beginners, tutorial, algorithms, leetcode
Published: 2023-09-08 17:11:18

Hey Guys! This is day 97 and we are back with another linked list problem.

---

## Removing Elements from a Linked List

In this article, we will be covering a C++ solution for removing all occurrences of a specific value from a singly-linked list. Let's get down to the problem.

## Problem: [Remove Linked List Elements](https://leetcode.com/problems/remove-linked-list-elements/)

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`.

---

### Example 1:

![Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1tilqlpurvoxprbef1z1.png)

> **Input:** head = [1,2,6,3,4,5,6], val = 6
> **Output:** [1,2,3,4,5]

---


## Understanding the Approach(Intuition)

Before diving into the code, let's understand the intuition behind the approach used in the provided C++ code.

- A `dummy` node is created at the beginning of the list. This simplifies the code, as it will allow us to handle cases where the first node of the original list contains the value to be removed.

- We initialize a `prev` previous pointer to point to the `dummy` node and a `curr` pointer to point to the head of the list.

- We iterate through the list using a `while` loop until we reach the end of the list.

- Inside the loop, we check if the `val` of the current node matches the value we want to remove (`val`). If it does, we update the `next` pointers to remove the node and free the memory.

- If the `val` does not match, we simply move the `prev` and `curr` pointers to the next nodes.

- Finally, we return the modified list without the `dummy` node.

## Dry Run Example Walkthrough

Let's perform a step-by-step walkthrough of the code with an example linked list: `1 -> 2 -> 6 -> 3 -> 4 -> 5`, and `val = 3`.

1. Initially, a `dummy` node is created, and `prev` is set to `dummy`. The list is: `dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5`.

2. The `prev` pointer remains at `dummy`, and `curr` is set to `1`.

3. Inside the loop, `curr` is checked. Since `curr->val` (which is `1`) does not match `val` (which is `3`), we move both `prev` and `curr` one step forward.

4. We continue this process. When `curr` reaches the node with `val = 3`, we update the `next` pointers to remove the node and free its memory. The list becomes: `dummy -> 1 -> 2 -> 6 -> 4 -> 5`.

5. The loop continues until the end of the list is reached.

6. Finally, the modified list is returned without the `dummy` node.

---

## Code

```cpp
public:
    ListNode* removeElements(ListNode* head, int val) {
    if (head == nullptr) {
        return head;
    }

    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* prev = dummy;
    ListNode* curr = head;

    while (curr != nullptr) {
        if (curr->val == val) {
            prev->next = curr->next;
            delete curr;
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }

    return dummy->next;
}

```

---

## Complexity Analysis:

### Time Complexity:

- Traversing of linked list at least one time leads to O(N) complexity where N is length of linked list.

- Overall, the time complexity is **O(N)**.

### Space Complexity

- Only use pointers slow and fast to solve the problem hence only constant space added.

- Overall, the space complexity is **O(1)**.