当前位置：首页 > news >正文

[E单调栈] lc2487. 从链表中移除节点(单调栈+递归+反转链表+多思路)

news 来源：原创 2024/5/3 6:17:28

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

链接：2487. 从链表中移除节点

2. 题目解析

本题还是有很多种做法的，题目看到之后就直接采用了单调栈处理了下，然后逆序的问题可以采用链表头插法，或者反转链表即可。写完看到题解区还有递归，先反转链表再进行业务处理，等等写法，算法思路不同，可以借鉴学习一下。

反转思路：

先对链表做一下反转。
从右向左遍历链表，找到比当前元素大的节点才加入，否则抛弃当前节点。
最后对链表再做一下反转即可。
可以学习一下官解中，反转链表的简约写法。

递归思路：

既然需要倒着的最大值，那么可以递归处理，递归后的回溯过程，就是从后向前的过程。
如果当前的 head 大于 node，则将 head->next = node 即可。
否则，直接删除 head 节点，return node 节点即可。在下一次回溯的的时候，就将跳过 head 节点。

着重看看递归思路，想一下，如果需要逆序打印链表元素，其实就很容易想到递归了。

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

/*** 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* reverseList(ListNode *head) {if (!head) return head;auto a = head, b = a->next;while (b) {auto c = b->next;b->next = a;a = b;b = c;}head->next = NULL;return a;}ListNode* removeNodes(ListNode* head) {stack<int> s;for (auto p = head; p; p = p->next) {while (s.size() && s.top() < p->val) s.pop();s.push(p->val);}ListNode *h = new ListNode(-1), *t = h;while (s.size()) {t = t->next = new ListNode(s.top());s.pop();}return reverseList(h->next);}
};

反转链表简约写法，其实没啥大区别，使用三指针反转链表即可：

    ListNode *reverse(ListNode *head) {ListNode dummy;while (head != nullptr) {ListNode *p = head;head = head->next;p->next = dummy.next;dummy.next = p;}return dummy.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}head->next = node; // 不删除 headreturn head;}
};