What is the most efficient approach for Next Greater Node In Linked List?

Convert the linked list into an array and use a monotonic decreasing stack to track nodes without known next greater values, achieving O(n) time.

Can this pattern be applied to arrays directly?

Yes, the monotonic stack approach works directly on arrays, but mapping from a linked list requires initial conversion to preserve order.

Why do we need a stack for this problem?

The stack tracks nodes whose next greater value hasn’t been determined yet, allowing efficient updates as larger values are encountered.

What happens if a node has no next greater node?

Any node remaining in the stack after full traversal has no next greater node, and its corresponding array entry is set to 0.

How does this solution avoid O(n^2) traversal?

Each node is pushed and popped from the stack at most once, ensuring linear traversal instead of checking every subsequent node for each element.

#1019

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

链表中的下一个更大节点

给定一个长度为 n 的链表 head 对于列表中的每个节点，查找下一个更大节点的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i…

数组链表栈单调栈

题目描述

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]

示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

提示：

链表中节点数为 n
1 <= n <= 10⁴
1 <= Node.val <= 10⁹

lightbulb

解题思路

方法一：单调栈

题目要求找到链表中每个节点的下一个更大的节点，即找到链表中每个节点的右边第一个比它大的节点。我们先遍历链表，将链表中的值存入数组 $nums$ 中。那么对于数组 $nums$ 中的每个元素，我们只需要找到它右边第一个比它大的元素即可。求下一个更大的元素的问题可以使用单调栈来解决。

我们从后往前遍历数组 $nums$ ，维护一个从栈底到栈顶单调递减的栈 $stk$ ，遍历过程中，如果栈顶元素小于等于当前元素，则循环将栈顶元素出栈，直到栈顶元素大于当前元素或者栈为空。

如果此时栈为空，则说明当前元素没有下一个更大的元素，否则当前元素的下一个更大的元素就是栈顶元素，更新答案数组 $ans$ 。然后将当前元素入栈，继续遍历。

遍历结束后，返回答案数组 $ans$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为链表的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        stk = []
        n = len(nums)
        ans = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and stk[-1] <= nums[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1]
            stk.append(nums[i])
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each node is pushed and popped at most once from the stack. Space complexity is O(n) for storing the array of node values and the stack.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Expecting use of a monotonic stack to efficiently track next greater elements in a linked list context.
question_mark
Looking for correct handling of node indexing when mapping linked list to array.
question_mark
Assessing understanding of linear-time solutions versus naive O(n^2) traversal approaches.

warning

常见陷阱

外企场景

error
Forgetting to convert the linked list into an array first, which complicates index-based stack management.
error
Incorrectly popping from the stack too early or late, leading to wrong next greater assignments.
error
Failing to set remaining nodes to 0 after stack processing, resulting in incomplete output.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding next smaller node instead of next greater, adjusting stack condition accordingly.
arrow_right_alt
Applying the pattern to a circular linked list where next greater may wrap around to the start.
arrow_right_alt
Handling multiple linked lists simultaneously, requiring separate stacks or merged tracking.

help

常见问题

外企场景

继续练习

#1008 前序遍历构造二叉搜索树 #975 奇偶跳 #962 最大宽度坡