ListNode 2487. 从链表中移除节点，单调栈的应用

一、题目

1、题目描述

给你一个链表的头节点 head 。

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head 。

2、接口描述

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNodes(ListNode* head) {}
};

3、原题链接

2487. 从链表中移除节点

---

二、解题报告

1、思路分析

可见题目要求我们把原链表修改为一个非升序链表，那么我们只需要遍历一遍链表，维护一个单调栈存储节点，保证从栈底到栈顶单调递减，遍历完之后将栈中节点串联起来，栈底节点就是表头

2、复杂度

时间复杂度：O(n) 空间复杂度：O(1)

3、代码详解

​

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNodes(ListNode* head) {if(!head || !(head -> next))return head;stack<ListNode*> s;s.push(head);head = head -> next;while(head){while(s.size() && head -> val > s.top() -> val)s.pop();s.push(head);head = head -> next;}while(s.size()){s.top() -> next = head;head = s.top();s.pop();}        return head;}
};