DAY 97 - Removing Elements from a Linked List

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

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:

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

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