MediumNo. 1019
Next Greater Node In Linked List — LeetCode 1019 Python Solution
- Pattern
- Linked List
- Topics
- Stack, Array, Linked List, Monotonic Stack
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given the head of a linked list with n nodes. For each node in the list, find the value of the next greater node.
Example
- Input
- head = [2,1,5]
- Output
- [5,5,0]
Python solution
# 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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1019. Next Greater Node In Linked List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2289 | Steps to Make Array Non-decreasing | Medium |
| 0084 | Largest Rectangle in Histogram | Hard |
| 0456 | 132 Pattern | Medium |
| 0503 | Next Greater Element II | Medium |
| 0654 | Maximum Binary Tree | Medium |
| 0739 | Daily Temperatures | Medium |
Frequently asked questions
- How hard is LeetCode 1019. Next Greater Node In Linked List?
LeetCode 1019. Next Greater Node In Linked List is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1019. Next Greater Node In Linked List?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1019. Next Greater Node In Linked List?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1019. Next Greater Node In Linked List cover?
LeetCode 1019. Next Greater Node In Linked List is tagged Stack, Array, Linked List and Monotonic Stack on LeetCode.