Saturday, December 2, 2023
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.

Related Links

Linked List Series #1 – Introduction – Creating a Linked list

Linked List Insertion – Linked List Tutorial Series #2

Linked List Deletion – Linked List Tutorial Series #3

 

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:


# find next greater node and print it
# eg:
# Input: [2,1,5]
# Output: [5,5,0]
# Definition for singly-linked list.
from typing import List
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
position = 1
stack, ans = [], [] # declaring empty lists
while head:
position += 1
ans.append(0)
# checking the top item of stack. Here -1 represents top most item
# and 1 represent the tuple's second item, i.e. value
while stack and stack[1][1] < head.val:
index, value = stack.pop() # popping the top item of the stack
ans[index] = head.val # appending the value to our answer list
stack.append((position, head.val)) # adding a tuple to the stack
head = head.next
return ans
if __name__ == "__main__":
a = ListNode(4)
b = ListNode(3)
c = ListNode(2)
d = ListNode(5)
a.next = b
b.next = c
c.next = d
x = Solution().nextLargerNodes(a)
for i in x:
print(i)

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
Vamsi Tallapudi
Architect Technology at Cognizant | Full Stack Engineer | Technical Blogger | AI Enthusiast

LEAVE A REPLY

Please enter your comment!
Please enter your name here

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

LATEST POSTS

House Robber Problem | Maximum Sum of non-adjacent elements

In this blog post, we will discuss about how to find maximum sum of Non-Adjacent elements. Since House Robber Problem is a typical DP Problem...
00:11:41

Check Array Formation Through Concatenation | Leetcode Problem 1640

In this video, we will explain Check Array Formation Through Concatenation, Leetcode's 1640th problem in 2 different approaches along with a coding solution. Problem statement You are given...

Binary Tree Traversals in Kotlin – PreOrder, InOrder and PostOrder Traversals

Binary Tree Traversals are most common Tree Problems in an Interview as well as Competitive Programming. They can be efficient while searching, inserting and deleting...

Linked List Deletion – Linked List Tutorial Series #3

In this article, we will discuss about linked list deletion. We will see how to delete a node in a Singly linked list. This article will...

Follow us

1,358FansLike
10FollowersFollow
399SubscribersSubscribe

Most Popular