贵州省遵义市住房城乡建设局网站,浏览器打开网址,网站建设分金手指排名二七,专门做产品推广ppt的网站【LetMeFly】2487.从链表中移除节点#xff1a;单调栈
力扣题目链接#xff1a;https://leetcode.cn/problems/remove-nodes-from-linked-list/
给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。 示例 1#xff1a; 输…【LetMeFly】2487.从链表中移除节点单调栈
力扣题目链接https://leetcode.cn/problems/remove-nodes-from-linked-list/
给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。 示例 1 输入head [5,2,13,3,8]
输出[13,8]
解释需要移除的节点是 5 2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。示例 2
输入head [1,1,1,1]
输出[1,1,1,1]
解释每个节点的值都是 1 所以没有需要移除的节点。提示
给定列表中的节点数目在范围 [1, 105] 内1 Node.val 105
方法一单调栈
维护一个单调递减栈严格地说是单调非递增栈 遍历链表在当前节点大于栈顶节点时不断弹出栈顶节点然后将当前节点入栈。 最终从栈底到栈顶的元素就是非递增的了。因此也就得到了想要的链表。
时间复杂度 O ( l e n ( l i s t n o d e ) ) O(len(listnode)) O(len(listnode))空间复杂度 O ( l e n ( l i s t n o d e ) ) O(len(listnode)) O(len(listnode))
然后被丢弃节点的delete操作就靠力扣了hh。
AC代码
C
class Solution {
public:ListNode* removeNodes(ListNode* head) {stackListNode* st;while (head) {while (st.size() st.top()-val head-val) {st.pop();}st.push(head);head head-next;}ListNode* lastNode nullptr;while (st.size()) {ListNode* thisNode st.top();st.pop();thisNode-next lastNode;lastNode thisNode;}return lastNode;}
};Python
class Solution:def removeNodes(self, head: ListNode) - ListNode:st []while head:while len(st) and st[-1].val head.val:st.pop()st.append(head)head head.nextfor i in range(len(st) - 1):st[i].next st[i 1]return st[0]同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/135357617
