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

2024-01-03 11:11:21

一、题目

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

文章来源:https://blog.csdn.net/EQUINOX1/article/details/135355127
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。