LeetCode 2487中等链表/单调栈
从链表中移除节点 图解题解
这道题到底在问什么
给定链表 head,移除所有「右侧存在值严格更大的节点」的节点,返回处理后链表的头。等价地说:只保留那些右边再没有比它更大的节点。
- 输入
- head = [5,2,13,3,8]
- 输出
- [13,8]
- 输入
- head = [1,2,3]
- 输出
- [3]
- 输入
- head = [3,2,1]
- 输出
- [3,2,1]
最优解：一步一步想明白
- 3记住:新值能压倒的栈顶都得移除(它右边有更大的),压不倒就停、把自己压栈。下面逐帧套它。
- 4遍历链表:读到第 1 个节点(值 5),抄进数组 vals 的下标 0。
- 5遍历链表:读到第 2 个节点(值 2),抄进数组 vals 的下标 1。
- 6遍历链表:读到第 3 个节点(值 13),抄进数组 vals 的下标 2。
- 7遍历链表:读到第 4 个节点(值 3),抄进数组 vals 的下标 3。
- 8遍历链表:读到第 5 个节点(值 8),抄进数组 vals 的下标 4。链表读完,vals 已就绪,下面切到数组上跑单调栈。
- 9vals 抄好了:柱子高度 = 节点值,柱子下方数字 = 下标。从左到右扫一遍,空栈起步,栈里维护「目前还该保留」的下标。
- 10轮到下标 0(高 5,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
- 11栈已空,没有可移除的。把当前下标 0 压栈(暂时保留它),继续往右扫。此刻保留栈 = [0],已移除 = [无]。
- 12轮到下标 1(高 2,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
- 13栈顶下标 0(高 5)不比 2 矮(5 ≥ 2),停止弹出。把当前下标 1 压栈(暂时保留它),继续往右扫。此刻保留栈 = [0, 1],已移除 = [无]。
- 14轮到下标 2(高 13,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
- 15栈顶是下标 1(高 2,标红),它严格小于当前的 13,说明 1 号节点右边冒出了更大的 13,1 号(值 2)必须移除,从栈里弹出。
- 16栈顶是下标 0(高 5,标红),它严格小于当前的 13,说明 0 号节点右边冒出了更大的 13,0 号(值 5)必须移除,从栈里弹出。
- 17栈已空,没有可移除的。把当前下标 2 压栈(暂时保留它),继续往右扫。此刻保留栈 = [2],已移除 = [0, 1]。
- 18轮到下标 3(高 3,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
- 19栈顶下标 2(高 13)不比 3 矮(13 ≥ 3),停止弹出。把当前下标 3 压栈(暂时保留它),继续往右扫。此刻保留栈 = [2, 3],已移除 = [0, 1]。
- 20轮到下标 4(高 8,紫色)。先反复比对栈顶:看有没有比它矮、会被它压倒的栈顶。
- 21栈顶是下标 3(高 3,标红),它严格小于当前的 8,说明 3 号节点右边冒出了更大的 8,3 号(值 3)必须移除,从栈里弹出。
- 22栈顶下标 2(高 13)不比 8 矮(13 ≥ 8),停止弹出。把当前下标 4 压栈(暂时保留它),继续往右扫。此刻保留栈 = [2, 4],已移除 = [0, 1, 3]。
- 23扫完整条数组。保留栈里是下标 2, 4(蓝色,值 13、8),高度从栈底到栈顶不增;灰色的下标 0、1、3 都因为右边有更大值被移除了。保留的就是答案。
- 24把结论映射回原链表:下标 0、1、3(值 5、2、3)被移除(灰),它们右边都存在更大的节点。
- 25把保留的节点按原顺序接起来,就是结果链表 13→8。回头看:我们只把链表抄了一遍、又扫了一遍数组,每个下标进栈出栈各一次,O(n) 就定出了该留谁。
⚠️ 容易写错的地方
✗ 错：弹栈用「小于等于」
✓ 对：严格小于才弹(栈顶 < 当前值)
题目只移除「右边有更大值」的;相等不算更大,相等的节点要保留,用 ≤ 会把相等的也错误移除
✗ 错：把「保留」理解成保留更小的
✓ 对：保留的是「右边没有更严格大值」的,结果序列不增
被新的更大值压倒的才移除;留下来的从左到右是不增的
✗ 错：反转法忘了断尾 / 忘了反转回
✓ 对：tail.next 置空,最后再 rev 一次
不断尾会接上已被移除的旧节点;不反转回则顺序是反的
完整代码（Python / C++ / Java）
Python
from typing import Optional, List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
def rev(node):
prev = None
while node:
nxt = node.next
node.next = prev
prev = node
node = nxt
return prev
head = rev(head)
dummy = ListNode(0)
tail = dummy
best = -10**18
cur = head
while cur:
nxt = cur.next
if cur.val >= best:
best = cur.val
tail.next = cur
tail = cur
cur = nxt
tail.next = None
return rev(dummy.next)C++
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
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 {
ListNode* rev(ListNode* node) {
ListNode* prev = nullptr;
while (node) { ListNode* nxt = node->next; node->next = prev; prev = node; node = nxt; }
return prev;
}
public:
ListNode* removeNodes(ListNode* head) {
head = rev(head);
ListNode dummy(0), *tail = &dummy;
int best = -1000000000;
while (head) {
ListNode* nxt = head->next;
if (head->val >= best) { best = head->val; tail->next = head; tail = head; }
head = nxt;
}
tail->next = nullptr;
return rev(dummy.next);
}
};Java
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
private ListNode rev(ListNode node) {
ListNode prev = null;
while (node != null) { ListNode next = node.next; node.next = prev; prev = node; node = next; }
return prev;
}
public ListNode removeNodes(ListNode head) {
head = rev(head);
ListNode dummy = new ListNode(0), tail = dummy;
int best = Integer.MIN_VALUE;
while (head != null) {
ListNode next = head.next;
if (head.val >= best) { best = head.val; tail.next = head; tail = head; }
head = next;
}
tail.next = null;
return rev(dummy.next);
}
}复杂度
时间
O(n)
单调栈视角:每个下标进栈一次、出栈一次,均摊线性。等价代码:两次反转 + 一次遍历,也是 O(n)
空间
O(n)
单调栈最坏(整体不增时)装下全部节点。等价代码原地反转是 O(1) 额外空间,这里按单调栈口径记 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 从链表中移除节点 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么单调栈能一遍就定出保留谁?+
因为每个节点是否保留,只取决于它右边有没有更大的值。单调栈从左到右扫,新值一来就把栈里所有被它压倒的(更矮的)一次性移除,这些移除后再也不会回来;每个下标进出栈各一次,所以总开销 O(n),一遍扫完栈里剩的就是答案。
反转法和单调栈是什么关系?+
完全等价。反转后从头扫、维护前缀最大值 best、只留 ≥ best 的,这个「前缀最大」在反序里,正好对应原序中「右边的最大值」;而单调栈是在正序里直接用栈顶比较。两者保留的是同一批节点,复杂度都是 O(n),只是实现风格不同。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 从链表中移除节点 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。