删除右侧值更大的节点 [英] Delete nodes which have a greater value on right side

问题描述

删除右侧值更大的节点

给出一个单链表，删除右侧值更大的所有节点。

Given a singly linked list, remove all the nodes which have a greater value on right side.

示例：

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

a) The list 12->15->10->11->5->6->2->3->NULL should be changed to 15->11->6->3->NULL. Note that 12, 10, 5 and 2 have been deleted because there is a greater value on the right side.

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

When we examine 12, we see that after 12 there is one node with value greater than 12 (i.e. 15), so we delete 12. When we examine 15, we find no node after 15 that has value greater than 15 so we keep this node. When we go like this, we get 15->6->3

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

b) The list 10->20->30->40->50->60->NULL should be changed to 60->NULL. Note that 10, 20, 30, 40 and 50 have been deleted because they all have a greater value on the right side.

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

c) The list 60->50->40->30->20->10->NULL should not be changed.

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

I have written the function for it. But it's not working.

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

推荐答案

算法这是我的算法，时间复杂度为 O（n）

Algorithm Here is My Algorithm which time complexity is O(n)

1. 反转列表。

1. Reverse the list.

遍历反转的列表。保持最大到现在为止。如果下一个节点< max，然后删除下一个节点，否则max =下一个节点。

Traverse the reversed list. Keep max till now. If next node < max, then delete the next node, otherwise max = next node.

再次反转列表以保留原始顺序。

Reverse the list again to retain the original order.

void reverseList(struct node **headref);
void _delLesserNodes(struct node *head);

/* Deletes nodes which have a node with greater value node
on left side */
void delLesserNodes(struct node **head_ref)
{
    /* 1) Reverse the linked list */
    reverseList(head_ref);

    /* 2) In the reversed list, delete nodes which have a node
         with greater value node on left side. Note that head
         node is never deleted because it is the leftmost node.*/
    _delLesserNodes(*head_ref);

   /* 3) Reverse the linked list again to retain the
         original order */
    reverseList(head_ref);
}

/* Deletes nodes which have greater value node(s) on left side */
void _delLesserNodes(struct node *head)
{
    struct node *current = head;

    /* Initialize max */
    struct node *maxnode = head;
    struct node *temp;

    while (current != NULL && current->next != NULL)
    {
         /* If current is smaller than max, then delete current */
         if(current->next->data < maxnode->data)
         {
              temp = current->next;
              current->next = temp->next;
              free(temp);
         }

         /* If current is greater than max, then update max and
            move current */
         else
         {
              current = current->next;
              maxnode = current;
         }

    }
}
//***********************************************

void reverseList(struct node **headref)
{
    struct node *current = *headref;
    struct node *prev = NULL;
    struct node *next;
    while(current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *headref = prev;
}

请让我知道，如果有任何错误。

Please Let me know, if there any mistake.

这篇关于删除右侧值更大的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！