c - 消除链表中的无序

Question

我正在尝试做一个练习，我必须确保链接列表中的所有元素都是有序的(本质上列表应该按升序排列)，如果任何元素大于下一个元素，它将被删除并释放从内存里。这是我当前的尝试:

struct node *remove_disorder(struct node *head) {
    struct node *curr = head;
    struct node *prev = head;


    if (curr == NULL) {
        return NULL;
    }
    if (curr->next == NULL) {
        return head;
    }

    struct node *temp = NULL;
    while (curr->next != NULL) {
        while (curr->data > curr->next->data) {
            if (curr == head) {
                prev = curr->next;
                free(curr);
                curr = prev;
                curr->next = prev->next;
                head = prev;
            } else {
                prev->next = curr->next;
                temp = curr;
                curr = prev;
                curr->next = prev->next;
                free(temp);
            }
        }
        prev = curr;
        curr = curr->next;

    }
    return head;
}

编译器告诉我，我正在 while (curr->data > curr->next->data) 中访问已释放的内存，即使我在释放 curr 后为其分配了一个新值。有人可以指出我做错了什么吗？

Answer 1

您的代码有一些多余的分配。 node2 = node1 赋值后，无需再赋值 node2->next = node1->next。

while (curr->next != NULL) {
    while (curr->data > curr->next->data) {
        if (curr == head) {
            prev = curr->next;
            free(curr);
            curr = prev; // after this line (see next comment)...
            curr->next = prev->next; // you do not need this.
            head = prev;
        } else {
            prev = curr->next; // '->next' removed
            temp = curr;
            curr = prev;
            curr->next = prev->next; // needless
            free(temp);
        }
    }

    // tough above code already assigned the next node to curr,
    // below code takes another step forward w/o any test.
    // nested while loops mess here.
    prev = curr; 
    curr = curr->next;
}

我认为，嵌套的 while 也是多余的。我选择的代码是:

while (curr->next != NULL) {
  if (curr->data <= (curr->next)->data) {
    curr = curr->next;
  }
  else {
    if (curr == head) {
      head = curr->next;
      free(curr);
      curr = head;
    }
    else {
      temp = curr;
      curr = curr->next;
      free(temp);
    }
  }
}