---
tags: leetcode
---

# [1019. Next Greater Node In Linked List](https://leetcode.com/problems/next-greater-node-in-linked-list/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

/**
 * Definition for singly-linked list.
 * 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 {
public:
    vector<int> nextLargerNodes(ListNode *head) {
        vector<int> nums;
        for (ListNode *curr = head; curr != nullptr; curr = curr->next) {
            nums.push_back(curr->val);
        }

        stack<int> st;
        vector<int> answer(nums.size(), 0);
        for (int i = 0; i < nums.size(); ++i) {
            while (!st.empty() && nums[st.top()] < nums[i]) {
                answer[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }

        return answer;
    }
};

## Time Complexity
$O(n)$
$n$ is the number of nodes in the linked list referred by `head`.
## Space Complexity
$O(n)$
# Miscellaneous
<!--
# Test Cases

[2,1,5]

[2,7,4,3,5]

[1,7,5,1,9,2,5,1]

* Wrong Answer

[3,3]

-->