CODEWITHSUNDEEP
c++linked-list
screw4445
screw4445

Reputation: 25

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

Upvotes: 2

Views: 629

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

This gets much easier if you can start at the end and work towards the head.

You can't do this directly with a singly-linked list, but you can use recursion.

First, if the list isn't empty, clean out the rest of the list.
Then you see if the node to the right is greater and remove it if it is.
And then you're done.

void scrub(digits* link)
{
    if (link != nullptr)
    {
        scrub(link->next);
        if (link->next != nullptr && link->next->value > link->value)
        {
            digits* scrap = link->next;
            link->next = link->next->next;
            delete scrap;
        }
    }
}

Upvotes: 2

Saurav Sahu
Saurav Sahu

Reputation: 13934

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

Upvotes: 1

Related Questions