screw4445 screw4445 - 1 month ago 7
C++ Question

Removing nodes from linked list not working properly

I have a problem with deleting nodes in linked list. This is my code (except for

addElement
function which works fine). I initialize nodes in the list trough input, then call the function which removes the nodes on right side with higher value and then print the modified list, lastly delete the list.
The problem is that with certain inputs my program doesn't work properly.
For example if I input 1,2,3,4,3 then the output should be 1 and 3 (the 2nd three) but my output is only 1.

What could be the problem? Can't seem to figure it out.

Edit 1: Here's the includes.
Edit 2: Included the addElement function

#include <iostream>
#include <stdlib.h>
#include <stdio.h>

struct digits {
int value;
digits *next
};

int main() {

int a, b, c;

digits *head = NULL, *tale = NULL, *current;
cout << "How many digits you want in the linked list?" << endl;
cin >> a;

for (int i = 0; i < a; i++) {
cin >> b;
current = new digits;
current->value = b;
current->next = NULL;
if (head == NULL)
head = tale = current;
else {
tale->next = current;
tale = current;
}
if (!cin.good()) {
cin.clear();
cin.ignore(256, '\n');
cout << "Input can be int value! You can still input " << (a - i) - 1
<< " digits." << endl;
continue;
}
}

cout << "Want to add element? Press J if so, otherwise any other key" << endl;
cin >> add;
if (add == 'J') {
cin >> c;
addElement(&head, c);
}

removeElement(head);

for (current = head; current != NULL; current = current->next)
cout << current->value << endl;
current = head;

while (current != NULL) {
head = head->next;
delete current;
current = head;
}
}

// function which removes elements which have greater value on right side
void removeElement(struct digits *head) {

struct digits *current = head;
struct digits *max = head;
struct digits *temp;

while (current != NULL && current->next != NULL) {
if (current->next->value > max->value) {
temp = current->next;
current->next = temp->next;
free(temp);
} else {
current = current->next;
max = current;
}
}
}
void addElement(struct digits **head, int a) {

struct digits *newelem = (struct digits*) malloc(sizeof (struct digits));
newelem->value = a;
newelem->next = NULL;
struct digits *temp = *head;
if (*head == NULL) {
*head = newelem;
} else {
while (temp->next != NULL)
temp = temp->next;
temp->next = newelem;
}
}

Answer

Why your code won't work:

Have a close look at this code:

while (current != NULL && current->next != NULL) {
    if (current->next->value > max->value) {
      temp = current->next;
      current->next = temp->next;
      free(temp);
    }

You are changing current but not max. Having max var in your code seems totally irrelevant.

Actually you never enter into the else part of the code, current value is always compared with max which throughout remains fixed at 1, and eventually while loop finishes when current is the last node(value = 3), as current->next != NULL fails for last node. So, it fails to get rid of last node. As a result of that, you get:

1(first node) and 3(last node)


Solution: Try this iterative approach:

Node *last, *lastTail = NULL;
current = *head;
int last_val = INT_MAX;
while (current != NULL) {
    if(current->value > last_val) {
        last = current;
        last_val = current->value;
        current = current->next;
        if(lastTail) {
            lastTail->next = current;
        }
        else {
            *head = current;
            lastTail = current;
        }
        delete last;
    }
    else{
        lastTail = current;
        last_val = current->value;
        current = current->next;
    }
}
Comments