Delete Nodes Which Have A Greater Value On Right Side

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
12 upvotes
Asked in company
Amazon

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?
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
8 7 8 4 5 6 2 1 -1
6 5 3 2 1 -1
Sample Output 1:
8 8 6 2 1 -1
6 5 3 2 1 -1
Explanation for sample input 1:
For the first test case, the given Linked List is

singly_linkedlist_input

So, the 2nd, 4th and the 5th nodes have greater values on their right sides. Hence, we delete these nodes. So, after deleting these nodes the Linked List becomes 8 → 8 → 6 → 2 → 1, which is shown in the below figure.

after_delete

For the second test case, the given Linked List is

singly_linkedlist_input

Since there are no such nodes that have greater values on the right sides, the Linked List remains unchanged.
Sample Input 2:
2
10 8 7 12 5 -1
5 6 7 8 10 12 -1
Sample Output 2:
12 5 -1
12 -1
Hint

Think of a brute force solution to check whether there exists a greater node on the right side for each node.

Approaches (3)
Brute-force

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.
Time Complexity

O(N ^ 2), where N is the total number of nodes in the Linked List.

 

Since for each node of the Linked List, we are traversing all the nodes starting from that node to the end of the Linked List. So, total N * (N + 1)/2 operations are being performed. Hence, the time complexity is O(N ^ 2).

Space Complexity

O(1)

 

Constant space is used.

Code Solution
(100% EXP penalty)
Delete Nodes Which Have A Greater Value On Right Side
Full screen
Console