Given a singly linked list where each node represents a character including special characters, the task is to remove all the occurrences of special characters from the linked list so that only valid characters are present in the linked list.
Examples:
Input: List = ( -> G -> E -> E -> * -> K -> S -> * -> NULL
Output: G -> E -> E -> K -> S -> NULLInput: A -> B -> C -> * -> @ -> NULL
Output: A -> B -> C -> NULL
Approach: Traverse the linked list. If the current node’s data is a special character, then make the next of the previous node point to the next of the current node. Do this for every node with a special character and finally print the updated list.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Structure for the node// of the linked liststruct node { char data; node* next;};// Utility function to add a new// node to the linked listnode* add(char data){ node* newnode = new node; // Assign the data to the data part // and assign NULL to the address part newnode->data = data; newnode->next = NULL; return newnode;}// Function to print the linked listvoid print(node* head){ while (head != NULL) { cout << head->data << " -> "; head = head->next; } cout << "NULL";}// Function that returns true if// ch is a special characterbool isSpecialChar(char ch){ // If lower-case character if (ch >= 'a' && ch <= 'z') return false; // If upper-case character if (ch >= 'A' && ch <= 'Z') return false; // If digit if (ch >= '0' && ch <= '9') return false; // ch is a special character return true;}// Function to remove the special// characters from the linked listnode* removeFromLL(node* head){ // Declare two variables curr and // prev both pointing to head node *curr = head, *prev = head; // The following loop removes special // characters from the head of the linked list // In case the special character is present at // the head of the linked list, make head point // to the next valid character while (curr != NULL && isSpecialChar(curr->data)) { node* temp = curr; head = curr->next; curr = curr->next; delete temp; } // Make prev point to head prev = head; // Repeat the process for // the entire Linked list while (curr != NULL) { // Repeat the process for all the elements // of linked list, in case a special character // is encountered then make the previous valid // character point to the next valid character // and remove the current node from the linked list while (curr != NULL && isSpecialChar(curr->data)) { node* temp = curr; prev->next = curr->next; curr = curr->next; delete temp; } // If the end is reached if (curr == NULL) break; prev = curr; curr = curr->next; } return head;}// Driver codeint main(){ // Create the linked list node* head = NULL; head = add('('); head->next = add('G'); head->next->next = add('E'); head->next->next->next = add('E'); head->next->next->next->next = add('*'); head->next->next->next->next->next = add('K'); head->next->next->next->next->next->next = add('S'); head->next->next->next->next->next->next->next = add('*'); // Remove the special characters // from the linked list head = removeFromLL(head); // Print the updated list print(head); return 0;} |
Java
// Java implementation of the approachclass GFG{// Structure for the node// of the linked liststatic class node{ char data; node next;};// Utility function to add a new// node to the linked liststatic node add(char data){ node newnode = new node(); // Assign the data to the data part // and assign null to the address part newnode.data = data; newnode.next = null; return newnode;}// Function to print the linked liststatic void print(node head){ while (head != null) { System.out.print(head.data + " -> "); head = head.next; } System.out.print("null");}// Function that returns true if// ch is a special characterstatic boolean isSpecialChar(char ch){ // If lower-case character if (ch >= 'a' && ch <= 'z') return false; // If upper-case character if (ch >= 'A' && ch <= 'Z') return false; // If digit if (ch >= '0' && ch <= '9') return false; // ch is a special character return true;}// Function to remove the special// characters from the linked liststatic node removeFromLL(node head){ // Declare two variables curr and // prev both pointing to head node curr = head; node prev = head; // The following loop removes special // characters from the head of the linked list // In case the special character is present at // the head of the linked list, make head point // to the next valid character while (curr != null && isSpecialChar(curr.data)) { node temp = curr; head = curr.next; curr = curr.next; temp = null; } // Make prev point to head prev = head; // Repeat the process for // the entire Linked list while (curr != null) { // Repeat the process for all the elements // of linked list, in case a special character // is encountered then make the previous valid // character point to the next valid character // and remove the current node from the linked list while (curr != null && isSpecialChar(curr.data)) { node temp = curr; prev.next = curr.next; curr = curr.next; temp = null; } // If the end is reached if (curr == null) break; prev = curr; curr = curr.next; } return head;}// Driver codepublic static void main(String[] args){ // Create the linked list node head = null; head = add('('); head.next = add('G'); head.next.next = add('E'); head.next.next.next = add('E'); head.next.next.next.next = add('*'); head.next.next.next.next.next = add('K'); head.next.next.next.next.next.next = add('S'); head.next.next.next.next.next.next.next = add('*'); // Remove the special characters // from the linked list head = removeFromLL(head); // Print the updated list print(head);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approachimport math # Structure for the node# of the linked listclass Node: def __init__(self, data): self.data = data self.next = None# Utility function to add a new# node to the linked listdef add(data): newnode = Node(data) # Assign the data to the data part # and assign None to the address part newnode.data = data newnode.next = None return newnode# Function to print the linked listdef printlist(head): while (head != None) : print(head.data, end = " -> ") head = head.next print("None")# Function that returns true if# ch is a special characterdef isSpecialChar(ch): # If lower-case character if (ch >= 'a' and ch <= 'z'): return False # If upper-case character if (ch >= 'A' and ch <= 'Z'): return False # If digit if (ch >= '0' and ch <= '9'): return False # ch is a special character return True# Function to remove the special# characters from the linked listdef removeFromLL(head): # Declare two variables curr and # prev both pointing to head curr = head prev = head # The following loop removes special # characters from the head of the linked list # In case the special character is present at # the head of the linked list, make head point # to the next valid character while (curr != None and isSpecialChar(curr.data)): temp = curr head = curr.next curr = curr.next temp = None # Make prev point to head prev = head # Repeat the process for # the entire Linked list while (curr != None): # Repeat the process for all the elements # of linked list, in case a special character # is encountered then make the previous valid # character point to the next valid character # and remove the current node from the linked list while (curr != None and isSpecialChar(curr.data)): temp = curr prev.next = curr.next curr = curr.next temp = None # If the end is reached if (curr == None): break prev = curr curr = curr.next return head# Driver codeif __name__=='__main__': # Create the linked list head = None head = add('(') head.next = add('G') head.next.next = add('E') head.next.next.next = add('E') head.next.next.next.next = add('*') head.next.next.next.next.next = add('K') head.next.next.next.next.next.next = add('S') head.next.next.next.next.next.next.next = add('*') # Remove the special characters # from the linked list head = removeFromLL(head) # Print the updated list printlist(head)# This code is contributed by Srathore |
C#
// C# implementation of the approachusing System; class GFG{// Structure for the node// of the linked listclass node{ public char data; public node next;};// Utility function to add a new// node to the linked liststatic node add(char data){ node newnode = new node(); // Assign the data to the data part // and assign null to the address part newnode.data = data; newnode.next = null; return newnode;}// Function to print the linked liststatic void print(node head){ while (head != null) { Console.Write(head.data + " -> "); head = head.next; } Console.Write("null");}// Function that returns true if// ch is a special characterstatic Boolean isSpecialChar(char ch){ // If lower-case character if (ch >= 'a' && ch <= 'z') return false; // If upper-case character if (ch >= 'A' && ch <= 'Z') return false; // If digit if (ch >= '0' && ch <= '9') return false; // ch is a special character return true;}// Function to remove the special// characters from the linked liststatic node removeFromLL(node head){ // Declare two variables curr and // prev both pointing to head node curr = head; node prev = head; // The following loop removes special // characters from the head of the linked list // In case the special character is present at // the head of the linked list, make head point // to the next valid character while (curr != null && isSpecialChar(curr.data)) { node temp = curr; head = curr.next; curr = curr.next; temp = null; } // Make prev point to head prev = head; // Repeat the process for // the entire Linked list while (curr != null) { // Repeat the process for all the elements // of linked list, in case a special character // is encountered then make the previous valid // character point to the next valid character // and remove the current node from the linked list while (curr != null && isSpecialChar(curr.data)) { node temp = curr; prev.next = curr.next; curr = curr.next; temp = null; } // If the end is reached if (curr == null) break; prev = curr; curr = curr.next; } return head;}// Driver codepublic static void Main(String[] args){ // Create the linked list node head = null; head = add('('); head.next = add('G'); head.next.next = add('E'); head.next.next.next = add('E'); head.next.next.next.next = add('*'); head.next.next.next.next.next = add('K'); head.next.next.next.next.next.next = add('S'); head.next.next.next.next.next.next.next = add('*'); // Remove the special characters // from the linked list head = removeFromLL(head); // Print the updated list print(head);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// javascript implementation of the approach // Structure for the node // of the linked listclass node { constructor() { this.data = ''; this.next = null; }} // Utility function to add a new // node to the linked list function add( data) { var newnode = new node(); // Assign the data to the data part // and assign null to the address part newnode.data = data; newnode.next = null; return newnode; } // Function to print the linked list function print( head) { while (head != null) { document.write(head.data + " -> "); head = head.next; } document.write("null"); } // Function that returns true if // ch is a special character function isSpecialChar( ch) { // If lower-case character if (ch >= 'a' && ch <= 'z') return false; // If upper-case character if (ch >= 'A' && ch <= 'Z') return false; // If digit if (ch >= '0' && ch <= '9') return false; // ch is a special character return true; } // Function to remove the special // characters from the linked list function removeFromLL( head) { // Declare two variables curr and // prev both pointing to head var curr = head; var prev = head; // The following loop removes special // characters from the head of the linked list // In case the special character is present at // the head of the linked list, make head point // to the next valid character while (curr != null && isSpecialChar(curr.data)) { var temp = curr; head = curr.next; curr = curr.next; temp = null; } // Make prev point to head prev = head; // Repeat the process for // the entire Linked list while (curr != null) { // Repeat the process for all the elements // of linked list, in case a special character // is encountered then make the previous valid // character point to the next valid character // and remove the current node from the linked list while (curr != null && isSpecialChar(curr.data)) { var temp = curr; prev.next = curr.next; curr = curr.next; temp = null; } // If the end is reached if (curr == null) break; prev = curr; curr = curr.next; } return head; } // Driver code // Create the linked list var head = null; head = add('('); head.next = add('G'); head.next.next = add('E'); head.next.next.next = add('E'); head.next.next.next.next = add('*'); head.next.next.next.next.next = add('K'); head.next.next.next.next.next.next = add('S'); head.next.next.next.next.next.next.next = add('*'); // Remove the special characters // from the linked list head = removeFromLL(head); // Print the updated list print(head);// This code contributed by gauravrajput1</script> |
Output:
G -> E -> E -> K -> S -> NULL
Time Complexity: O(N).
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
