c - 删除右侧值较大的节点

Question

删除右侧值较大的节点

给定一个单链表，删除右侧所有具有较大值的节点。

示例:

a) 列表 12->15->10->11->5->6->2->3->NULL 应更改为 15->11->6->3->NULL。请注意，12、10、5 和 2 已被删除，因为右侧的值更大。

当我们检查 12 时，我们发现 12 之后有一个节点的值大于 12(即 15)，因此我们删除 12。当我们检查 15 时，我们发现 15 之后没有值大于 15 的节点，因此我们保留该节点。当我们这样走时，我们得到 15->6->3

b) 列表 10->20->30->40->50->60->NULL 应更改为 60->NULL。请注意，10、20、30、40 和 50 已被删除，因为它们在右侧都有更大的值。

c) 列表 60->50->40->30->20->10->NULL 不应更改。

我已经为它编写了函数。但这不起作用。

void remove_lower(struct node** head_ref)
{
   struct node* current = (*head_ref);

   if(current != NULL && current->next != NULL)
     return ;

   struct node* temp;

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

Answer 1

您应该跟踪“上一个”项目并更新其“下一个”指针，否则您将在删除列表中不是第一个元素时破坏列表。此外，您的算法还会删除所有比当前元素“更大”的“下一个”元素。根据您的描述，如果“当前”元素的右侧有更大的元素，您将删除它。因此，您应该删除“当前”元素，而不是下一个元素。

我建议对该算法采用以下方法(在 ideone 检查)(不幸的是，O(N^2)):

void remove_lower(struct node** head_ref)
{
  struct node* current = (*head_ref);
  if(current == NULL || current->next == NULL)
    return ;

  struct node* prev = NULL, *next = NULL, *temp = NULL;
  while(current->next != NULL)
  {
    next = current->next;
    temp = next;
    /* check if there is any element greater than current */
    while(temp->next != NULL) {
        if (temp->data > current->data) {
            /* 
             * if some element is greater than current, then
             * delete current element
             */
            free(current);
            current = NULL;
            if (prev == NULL) {
                /* it was the first element, need to update the head */
                *head_ref = next;
            } else {
                prev->next = next;
            }
            break;
        }
        temp = temp->next;
    }
    /* if current element was not deleted */
    if (current != NULL) {
        prev = current;
    }
    current = next;
  }
}

输出:

输入数据:

2->7->1->36->6->0->5->-1->16->4->-2->3->-3->4->2->-4->1->-5->0->0->NULL

输出数据:

36->16->4->4->2->1->0->0->NULL