做完这道题的那个下午,我盯着测试用例发了好一会儿呆。
输入是 [5,2,13,3,8],输出变成 [13,8]。
被删掉的 5、2、3,全都有一个共同点——它们右侧存在一个比自己更大的数。
这道 LeetCode 第 2487 号题的任务很直白:给定一个单链表的头节点,移除所有满足“右侧任意位置存在更大节点值”这一条件的节点,最后返回修改后的链表。
用题目给的例子来拆解,你会立刻理解它在干什么。
链表 5 → 2 → 13 → 3 → 8。
节点 13 位于 5 和 2 的右侧,因此 5 和 2 必须移除。
节点 8 位于 3 的右侧,因此 3 必须移除。
最终留下来的,只有 13 和 8。
这个规则的残酷之处在于:一个节点能不能活下来,看的不是自己有多强,而是它身后有没有更强的存在。一旦某个右侧节点值更大,它就连带被清除出场。
解题思路里最精彩的一步,是先把这个单向链表翻转过来。
翻转之后,原本复杂的“向后看”直接变成了“向前看”——你只需要从翻转后的头节点开始,维护一个当前遇到的最大值,凡是遇到比它小的节点,统统跳过;遇到更大的,就更新最大值并保留该节点。
遍历完成后,再把处理好的链表翻转一次,恢复到原本的顺序。
代码实现里定义了一个名为 reverList 的辅助函数,用于执行链表翻转。主函数 removeNodes 的流程是三步走:
第一步,翻转原链表,得到 reversList;
第二步,用 maxNode 和 prevNode 配合 currNode 遍历翻转后的链表,执行上述的“保留历史最大值”过滤逻辑;
第三步,将过滤结果再次翻转,作为最终答案返回。
这个过滤逻辑的 while 循环写得极其克制:当 maxNode 的值大于 currNode 的值时,currNode 直接跳到下一个节点;否则,就把 maxNode 更新为 currNode,把 prevNode 的 next 指向 currNode,然后 prevNode 和 currNode 各自前进。
循环结束后,把 prevNode 的 next 设为 null,干净收尾。
这道题真正让我兴奋的地方,不在于它考了链表反转——那是基础操作。它巧妙在那层“往前看”的思维翻转:很多看起来需要反复回头才能解决的问题,一旦你调转方向,复杂度就当场降级。
2487 号题不会是你做过最难的链表题,但它很可能成为你面试时最想拿出来聊五分钟的那一道。
热门跟贴