从链表中删除节点无法正常工作

Question

我在删除链表中的节点时遇到问题。这是我的代码(除了addElement函数工作正常(。我通过输入初始化列表中的节点，然后调用函数，该函数删除右侧具有较高值的节点，然后打印修改后的列表，最后删除列表。问题是对于某些输入，我的程序无法正常工作。例如，如果我输入 1,2,3,4,3，那么输出应该是 1 和 3(第二个三个(，但我的输出只有 1。

可能是什么问题？似乎想不通。

编辑 1：这是包含的内容。编辑 2：包含 addElement 函数

#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 1

如果你能从最后开始，朝着头部努力，这会变得容易得多。

你不能直接使用单向链表来做到这一点，但你可以使用递归。

首先，如果列表不为空，请清除列表的其余部分。
然后，您会看到右侧的节点是否更大，如果是，则将其删除。
然后你就完成了。

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

Answer 2

为什么你的代码不起作用：

仔细看看这段代码：

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

您正在更改current但不是max.在代码中max var 似乎完全无关紧要。

实际上，您从未进入代码的else部分，current值总是与始终固定在1 max进行比较，最终while循环在current是最后一个节点(值= 3(时完成，因为最后一个节点current->next != NULL失败。因此，它无法摆脱最后一个节点。因此，您将获得：

1(第一个节点(

和 3(最后一个节点(

---

解决方案：尝试以下迭代方法：

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