Remove Linked List Elements - CPP Solution

1. Introduction

This blog post explores a common problem in linked list manipulation: removing all nodes from a linked list that have a specific value. This task tests one's ability to traverse and modify a linked list.

Problem

Given the head of a linked list and an integer val, the objective is to remove all nodes from the linked list that have Node.val == val, and then return the new head of the modified list.

2. Solution Steps

1. Handle edge cases where the list is empty or all nodes need to be removed.

2. Use two pointers, prev and current, to traverse the list.

3. Remove nodes with the target value by adjusting the next pointer of the prev node.

4. Return the new head of the list.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to remove elements from the list
ListNode* removeElements(ListNode* head, int val) {
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *prev = dummy, *current = head;

    while (current) {
        if (current->val == val) {
            prev->next = current->next;
            delete current; // Free memory
            current = prev->next;
        } else {
            prev = current;
            current = current->next;
        }
    }

    ListNode *newHead = dummy->next;
    delete dummy; // Free memory
    return newHead;
}

// Function to print the linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(6);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next->next = new ListNode(6);

    int val = 6;
    head = removeElements(head, val);
    printList(head); // Expected output: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
    return 0;
}

Output:

1 -> 2 -> 3 -> 4 -> 5 -> nullptr

Explanation:

The removeElements function creates a dummy node to simplify the removal of nodes, especially when the head node needs to be removed. The function then iterates over the list using two pointers, prev and current. If current points to a node with the target value, it is removed, and prev is updated to bypass the deleted node. If current does not have the target value, both pointers move forward. Finally, the function returns the new head of the list, ensuring all nodes with the target value are removed.