screw4445 - 1 year ago 55

C++ Question

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

`addElement`

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 Source

**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;
}
}
```