Last Updated: 5 Feb, 2021

Delete Nodes Which Have A Greater Value On Right Side

Moderate

Asked in company

Solve now

Problem statement

You are given a linked list of integers where each node has two fields: data field which contains a value, 'next' field which points to its adjacent node to the right or NULL if it is the last node. Your task is to delete all such nodes X, whose adjacent nodes to the right have strictly greater value than the value of X.

A singly linked list is a linear data structure in which we can traverse only in one direction i.e. from Head to Tail. It consists of several nodes where each node contains some data and a reference to the next node.

A sample Linked List-

singly_linkedlist

Follow Up:

Can you solve this in linear time and constant space complexity?

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.
For more clarity please refer to the sample inputs.

Output format:

For each test case, delete all the nodes which have a strictly greater value on the right side to this node.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
1 <= node.data <= 10^9 (node.data != -1) 

Time limit: 1 second

Solve now

Approaches

01 Approach

Approach:

Traverse each node of the Linked List and for each node run a loop from that node to the end of the Linked List to check whether there exists a node having a value greater than the current node. If such a node exists, then we delete the current node, else we just move on to the next node.

Steps:

If head is NULL or head.next is NULL, then simply return head.
Take 3 pointers named as p, newHead and prev. The pointer p is used to traverse the Linked List, pointer newHead is used to store the head of the resulting Linked List after performing the delete operations. And the pointer prev is used to store the last node of the resulting Linked List which is useful for the Linked List formation.
Make the pointer p to point to the head and newHead NULL initially.
Now, while p is not NULL, do:
- Create a temp node and assign it to p.
- Create another pointer to traverse the Linked List starting from p to the end of the Linked List. So Node *q = p.next.
- Create a boolean variable isGreaterOnRight in order to know whether there is a node having a greater value on the right side or not. Initialize it to false initially.
- While q is not NULL, do:
  - If q.data > p.data:
    - If newHead is not NULL, then prev.next = p.next.
    - Make p = p.next and delete the temp.
    - Make isGreaterOnRight = true and break out of the loop.
  - q = q.next.
- If isGreaterOnRight = false:
  - If newHead = NULL, then this is the first node, which doesn’t have a greater value on the right side. So, we assign this node to the newHead, which is the head of the resultant Linked List. So, newHead = p.
  - prev = p and p = p.next.
Finally, return newHead.

Solve now

02 Approach

Steps:

If the head is NULL or head.next is NULL, then simply return head.
Create a maximum variable and initialize it to INT_MIN.
Then call a recursive function by passing the head and the maximum value as reference, i.e. return deleteGreaterOnRight(head, &maximum).

Node *deleteGreaterOnRight(head):

If the head is NULL, then simply return the head.
Call the recursive function by passing the head.next as head and store the result in head.next, i.e. head.next = deleteGreaterOnRight(head.next, maximum).
If the value of the head is less than *maximum, then return head.next.
*maximum = max(*maximum, head.data).
Finally, return head.

Solve now

03 Approach

Approach:

Instead of finding a greater value for each node of the Linked List, we can find the suffix Max of the Linked List, and for each node, if the suffix Max is greater than the value of the current node, then we delete this node, else we keep it. For example, if the Linked List is 10 → 8 → 7 → 12 → 5. Then the suffixMax of all the elements should look like, [12, 12, 12, 12, 5]. So, as the value of the first three nodes is less than their respective suffix Max values, so we delete these three nodes. Since, unlike an array, we do not have direct access to all the nodes of the Linked List, in order to implement above the idea, we can just reverse the Linked List, store the prefix Max, and perform the above operations and then reverse the Linked List again.

Steps:

If the head is NULL or head.next is NULL, then simply return head.
Reverse the Linked List, i.e. head = reverse(head).
Implement the deleteGreaterOnRight(Node *head) function and store the result in head, i.e. head = deleteGreaterOnRight(head).
Reverse the Linked List again to restore the original order, i.e. head = reverse(head).
Finally, return the head.

Node *reverse(head):

If the head is NULL or head.next is NULL, then simply return head.
Take 3 pointers, named as prev, curr, and next. Initialize prev to NULL and curr to head.
While curr is not NULL, do:
- next = curr.next.
- curr.next = prev.
- prev = curr.
- curr = next.
Finally, return prev.

Node *deleteGreaterOnRight(head):

If the head is NULL or head.next is NULL, then simply return head.
Create a maximum variable and store the value of head.data in it and create a pointer p to traverse the Linked List.
While p is not NULL and p.next is not NULL:
- If p.next.data < maximum:
  - Create a temp pointer to store p.next.
  - p.next = p.next.next.
  - delete temp.
- Else:
  - maximum = p.next.data.
  - p = p.next.
Finally, return head.

Solve now