C++程序 删除右侧具有较大值的节点

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

例如：

输入: 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

输入: 10->20->30->40->50->60->NULL
输出: 60->NULL
解释: 10、20、30、40和50已被删除，因为它们的右侧都有更大的值。

输入: 60->50->40->30->20->10->NULL
输出: 无改变。

方法1（简单）：

使用两个循环。在外部循环中，逐个选择链表节点。在内部循环中，检查是否存在具有大于选定节点值的节点。如果存在大于选定节点值的节点，则删除选定节点。

时间复杂度： O(n^2)

方法2（使用反转）：

感谢Paras提供下面的算法。

1. 反转列表。

2. 遍历反转列表。保留当前的最大值。如果下一个节点小于最大值，则删除下一个节点，否则将最大值更新为下一个节点。

3. 反转列表以保留原始顺序。

时间复杂度： O(n)

// C++程序，删除右侧值更大的节点
//与左侧的节点。 
#include <bits/stdc++.h>
using namespace std;
 
//链表节点的结构 
struct Node
{
    int data;
    struct Node* next;
};
 
//实用函数原型 
void reverseList(struct Node** headref);
void _delLesserNodes(struct Node* head);
 
/*删除节点，这些节点具有左侧更高值的节点 
*/
void delLesserNodes(struct Node** head_ref)
{
    // 1. 反转链表 
    reverseList(head_ref);
 
    /* 2. 在已反转的列表中，删除具有更大
          的左侧节点的节点。请注意，头节点
          从未被删除，因为它是最左边的节点。 */    
    _delLesserNodes(*head_ref);
 
    /* 3. 再次反转链表以保持原始顺序 */ 
    reverseList(head_ref);
}
 
/*删除具有左侧更高值节点的节点*/
void _delLesserNodes(struct Node* head)
{
    struct Node* current = head;
 
    // 初始化最大值 
    struct Node* maxnode = head;
    struct Node* temp;
 
    while (current != NULL && current->next != NULL)
    {
        /*如果current比max更小，
          那就删除current */ 
        if (current->next->data < maxnode->data)
        {
            temp = current->next;
            current->next = temp->next;
            free(temp);
        }
 
        /*如果current比max更大，
          更新最大值并移动current*/ 
        else
        {
            current = current->next;
            maxnode = current;
        }
    }
}
 
/*实用函数，在头部插入节点*/
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}
 
/*实用函数，反转链接列表*/ 
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;
}
 
/*实用函数，打印链接列表*/
void printList(struct Node* head)
{
    while (head != NULL)
    {
        cout << " " << head->data ;
        head = head->next;
    }
    cout << "" ;
}
 
//驱动代码 
int main()
{
    struct Node* head = NULL;
 
    /* 创建以下链接列表
       12->15->10->11->5->6->2->3 */
    push(&head, 3);
    push(&head, 2);
    push(&head, 6);
    push(&head, 5);
    push(&head, 11);
    push(&head, 10);
    push(&head, 15);
    push(&head, 12);
 
    cout << "给定链接列表" ;
    printList(head);
 
    delLesserNodes(&head);
 
    cout << "修改后的链接列表" ;
    printList(head);
 
    return 0;
}
//此代码由shivanisinghss2110贡献```  

输出:

给定链接列表 
12 15 10 11 5 6 2 3
修改后的链接列表 
15 11 6 3

时间复杂度 ：O(n)

辅助空间 ：O(1)