Write a linear time C function which removes all occurrences of a given integer

Question

Write a linear time C function which removes all occurrences of a given integer x from the a linked list. (Note that there is no “wrapper” struct to deal with ­­ just work at the node pointer level). parameter lst is a pointer to the first node in the list parameter x is the value to be removed. the function returns a pointer to the first element of the resulting linked list. Full credit requires a linear time solution; partial credit will be granted for a correct but slower solution. Your solution may be recursive or non­recursive. Hint: recursion might be the simplest way to get this quickly.

typedef struct node_struct {

int val;

struct node_struct *next;

} NODE;

/*

example: removing all occurrences of x=5 from the list below

[2 4 9 5 5 2 4 5 5 9]

results in

[2 4 9 2 4 9]

*/

NODE *remove_all_x(NODE *lst, int x){

Explanation / Answer

#include <iostream>

using namespace std;

typedef struct llist
{
int data;
struct llist* next;
} llist;

/* This function takes an integer and head pointer of the unordered list with
duplicates and deletes all occurence of it from the list. It returns pointer to
the head after completion. */

llist* deleteNodesWithValue(int value, llist* head)
{
/*If list is NULL we don't have anything to do*/
if (!head)
{
return head;
}
  
/* Declare a previous and current pointer to take care of the previous
and current node in the list*/
llist* prev = NULL;
llist* current = head;
  
/*Take care of the case where leading nodes are value to be deleted*/
while (current && current->data == value)
{
prev = current;
current = current->next;
head = current;
delete prev;
}
/*At the end of above loop our new head is known which makes things simpler*/
/*Now we traverse the list from left to right*/
while (current)
{
if (current->data == value)
{
prev->next = current->next;
delete current;
current = prev->next;
}
else
{
prev = current;
current = current->next;
}
}
return head;
}

void printList(llist* head)
{
while (head)
{
cout << head->data << endl;
head = head->next;
}
}

int main()
{
cout << "Hello World" << endl;
int arr[] = { 2 ,2 ,8 ,9 ,7 ,2 ,2 ,2 ,6 ,1 ,5 ,2 ,2};
int i = 0;
int size = sizeof(arr)/sizeof(int);
llist* head = NULL;
llist* prev = NULL;
while (i < size) {
llist* newlist = new llist();
newlist->data = arr[i];
newlist->next = NULL;
if (!head)
{
head = newlist;
}
if (prev)
{
prev->next = newlist;
prev = newlist;
}
else
{
prev = newlist;
}
i++;
}
head = deleteNodesWithValue(2, head);
printList(head);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.