Monday, May 27, 2024
HomeAlgorithmsNext Greater node in a Linked List - Leetcode Problem #1019

# Next Greater node in a Linked List – Leetcode Problem #1019

-

In this article, we will discuss the solution for 1019th Problem from Leetcode – Next Greater Node In Linked List.

Let us see the question in brief before diving into the solution. Full question can be seen from this Leetcode link.

##### Problem

We are given a linked list with head as the first node. Let’s number the nodes in the list: node_1, node_2, node_3, … etc. Return an array of integersÂ `answer`, whereÂ `answer[i] = next_larger(node_{i+1})`.

Example:

```Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]```

So let us discuss the solution for the above problem.

##### 1. Naive approach

In this very basic approach, for each node, we will traverse through remaining all elements to the right of that node and check which is bigger than this node. We will then add to list and return it.

As we can see, the time complexity of this approach will be O(N).

Is there any better way to do this?

##### 2. Using Stacks

In this approach, we will make use of stack. Here, each item of the stack is a tuple which consists of two values -> index, value.

We will also keep an answer list to be returned as solution. We will increment the index variable at each iteration.

If the stack is not empty and the stack’s top value is less than the current node value of linked list, we will pop the top item and insert it into answer as ans[index] = value.

If stack’s top value is greater than current node of linked list, we will add the index and value of linked list to the stack.

##### Solution

The solution in Python is as follows:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

The code is commented wherever I find it necessary. Feel free to comment in case of any issues.

Do follow us for Coderefer newsletter to never miss an update from our Blog and YouTube channel. The video will be updated soon.

Vamsi Tallapudi
Architect Technology at Cognizant | Full Stack Engineer | Technical Blogger | AI Enthusiast

This site uses Akismet to reduce spam. Learn how your comment data is processed.

### Best Time to Buy and Sell Stock – Day 7 | 100 Days of Code

Welcome to Day 7 of 100 Days of Code where today we solve yet another most frequently asked easy array problem called - Best Time...

### Contains Duplicate – Day 8 | 100 Days of Code

Welcome to Day 8 of 100 Days of Code and today we are going to solve yet another easy-level problem - Contains Duplicate as part...

### Two Sum – Day 6 | 100 Days of Code

Welcome to Day 6 of 100 Days of Code where we solve the most frequently asked Easy level Array problem - Two Sum. Let us...

### Arrays for Beginners: Unveiling the Power of Data Structures

Hello, Programmers ðŸŒŸ Welcome to Coderefer! Let's explore the world of arrays together. Arrays are like handy data structures that help you manage and work...

1,358Fans
10Followers
398Subscribers