LeetCode 题解工作台
从链表中移除节点
给你一个链表的头节点 head 。 移除每个右侧有一个更大数值的节点。 返回修改后链表的头节点 head 。 示例 1： 输入： head = [5,2,13,3,8] 输出： [13,8] 解释： 需要移除的节点是 5 ，2 和 3 。 - 节点 13 在节点 5 右侧。 - 节点 13 在节点 …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们可以先将链表中的节点值存入数组 ，然后遍历数组 ，维护一个从栈底到栈顶单调递减的栈 ，如果当前元素比栈顶元素大，则将栈顶元素出栈，直到当前元素小于等于栈顶元素，将当前元素入栈。 最后，我们从栈底到栈顶构造出结果链表，即为答案。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个链表的头节点 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 <= 105
解题思路
方法一：单调栈模拟
我们可以先将链表中的节点值存入数组 ，然后遍历数组 ，维护一个从栈底到栈顶单调递减的栈 ，如果当前元素比栈顶元素大，则将栈顶元素出栈，直到当前元素小于等于栈顶元素，将当前元素入栈。
最后，我们从栈底到栈顶构造出结果链表，即为答案。
时间复杂度 ，空间复杂度 。其中 是链表的长度。
我们也可以不使用数组 ，直接遍历链表，维护一个从栈底到栈顶单调递减的栈 ，如果当前元素比栈顶元素大，则将栈顶元素出栈，直到当前元素小于等于栈顶元素。然后，如果栈不为空，则将栈顶元素的 指针指向当前元素，否则将答案链表的虚拟头节点的 指针指向当前元素。最后，将当前元素入栈，继续遍历链表。
遍历结束后，将虚拟头节点的 指针作为答案返回。
时间复杂度 ，空间复杂度 。其中 是链表的长度。
# Definition for singly-linked 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]:
nums = []
while head:
nums.append(head.val)
head = head.next
stk = []
for v in nums:
while stk and stk[-1] < v:
stk.pop()
stk.append(v)
dummy = ListNode()
head = dummy
for v in stk:
head.next = ListNode(v)
head = head.next
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited at most twice during traversal or stack operations. Space complexity is O(1) if pointers are updated in-place, or O(n) if using recursion or a stack to track nodes. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Focus on efficient pointer manipulation rather than creating new lists.
- question_mark
Consider reversing the list or using a monotonic stack to simplify removal logic.
- question_mark
Ensure consecutive nodes that need removal do not break list connectivity.
常见陷阱
外企场景- error
Failing to update next pointers correctly when multiple nodes are removed consecutively.
- error
Using nested loops leading to O(n^2) time instead of linear traversal.
- error
Not handling edge cases where the largest node is at the end or all nodes are equal.
进阶变体
外企场景- arrow_right_alt
Return the modified list without using any extra space beyond pointers.
- arrow_right_alt
Remove nodes that have a greater value immediately next instead of anywhere to the right.
- arrow_right_alt
Apply the same removal logic on a doubly linked list, adjusting both prev and next pointers.