Remove all nodes from the Linked List of given value

Given a singly linked list, the task is to remove all nodes that have a specific value. The function should handle cases efficiently, including removing the first node, removing nodes from the middle, and removing nodes from the end.

Input-Output Examples

Example 1:

  • Input:
    • List: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> NULL
    • Value: 6
  • Output: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Example 2:

  • Input:
    • List: 1 -> 1 -> 1 -> 2 -> 3 -> NULL
    • Value: 1
  • Output: 2 -> 3 -> NULL

Example 3:

  • Input:
    • List: 1 -> 2 -> 3 -> NULL
    • Value: 4
  • Output: 1 -> 2 -> 3 -> NULL

Approach:

To remove all nodes with a given value from the linked list, we can use a dummy node to handle edge cases efficiently. We will iterate through the list and unlink nodes that match the given value.

Steps to implement:

  1. Initialize a dummy node:
    • This dummy node will help handle edge cases, such as removing nodes from the head of the list.
    • Set the dummy node's next pointer to the head of the list.
  2. Traverse the list:
    • Use two pointers: current pointing to the dummy node and next_node pointing to the next node in the list.
    • Check if the value of next_node matches the given value.
    • If it does, update current.next to skip the node.
    • If it does not, move current to the next node.
  3. Return the modified list:
    • The head of the modified list will be dummy.next.

C++ Program to remove all the elements from the Linked List with given value

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to remove all nodes with a specific value
ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* current = &dummy;

    while (current->next != NULL) {
        if (current->next->val == val) {
            ListNode* temp = current->next;
            current->next = current->next->next;
            delete temp;
        } else {
            current = current->next;
        }
    }

    return dummy.next;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> NULL
    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);

    // Remove all elements with value 6
    head = removeElements(head, 6);
    cout << "After removing all elements with value 6: ";
    printList(head);

    return 0;
}

Java Program to remove all the elements from the Linked List with given value

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Main {
    // Function to remove all nodes with a specific value
    public static ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;

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

        return dummy.next;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> NULL
        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);

        // Remove all elements with value 6
        head = removeElements(head, 6);
        System.out.print("After removing all elements with value 6: ");
        printList(head);
    }
}

Python Program to remove all the elements from the Linked List with given value

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Function to remove all nodes with a specific value
def remove_elements(head, val):
    dummy = ListNode(0)
    dummy.next = head
    current = dummy

    while current.next is not None:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next

    return dummy.next

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(6)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(4)
head.next.next.next.next.next = ListNode(5)
head.next.next.next.next.next.next = ListNode(6)

# Remove all elements with value 6
head = remove_elements(head, 6)
print("After removing all elements with value 6:", end=" ")
print_list(head)

DSA

5555

478

Related Articles