题目描述
给你一个链表的头节点 head
。
对于列表中的每个节点 node
,如果其右侧存在一个具有 严格更大 值的节点,则移除 node
。
返回修改后链表的头节点 head
。
样例
输入:head = [5,2,13,3,8]
输出:[13,8]
解释:需要移除的节点是 5,2 和 3。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。
输入:head = [1,1,1,1]
输出:[1,1,1,1]
解释:每个节点的值都是 1 ,所以没有需要移除的节点。
限制
- 给定列表中的节点数目在范围
[1, 10^5]
内。 1 <= Node.val <= 10^5
算法
(递归) $O(n)$
- 递归遍历,如果递归后继节点的值比当前节点要大,则直接返回后继节点;否则设置当前节点的后继节点为递归的返回节点。
时间复杂度
- 每个节点遍历一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储递归系统栈空间。
C++ 代码
/**
* 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 == nullptr)
return nullptr;
ListNode *t = removeNodes(head->next);
if (t != nullptr && t->val > head->val)
return t;
head->next = t;
return head;
}
};