香河住房和建设局网站,做教育集团的网站,湖北省两学一做网站,广州天河建站公司2487. 从链表中移除节点
给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。
示例 1#xff1a; 输入#xff1a;head [5,2,13,3,8] 输出#xff1a;[13,8] 解释#xff1a;需要移除的节点是 5 #xff0c;2 和 3 。…2487. 从链表中移除节点
给你一个链表的头节点 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 1e5
既然题目要倒着看最大值明显可以用到递归,利用递归确定每个数右侧都是比他大的
/*** 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 - next nullptr) {return head;}ListNode* node removeNodes(head - next);if(node - val head - val) {return node;}head - next node;return head;}
};看完题解后还有另外的解法也就是单调栈
/*** 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) {ListNode* dummy new ListNode(0, head);ListNode* cur head;vectorListNode* stk;for (ListNode* cur head; cur; cur cur-next) {while (stk.size() stk.back()-val cur-val) {stk.pop_back();}if (stk.size()) {stk.back()-next cur;} else {dummy-next cur;}stk.push_back(cur);}return dummy-next;}
};灵神题解中还用了迭代来做
class Solution {ListNode *reverseList(ListNode *head) {ListNode *pre nullptr, *cur head;while (cur) {ListNode *nxt cur-next;cur-next pre;pre cur;cur nxt;}return pre;}
public:ListNode *removeNodes(ListNode *head) {head reverseList(head);ListNode *cur head;while (cur-next) {if (cur-val cur-next-val) {cur-next cur-next-next;} else {cur cur-next;}}return reverseList(head);}
};
