# LeetCode - Remove Nodes From Linked List

## Problem statement

You are given the `head` of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the `head` of the modified linked list.

Example 1:

``````Input: head = [5, 2, 13, 3, 8]
Output: [13, 8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
``````

Example 2:

``````Input: head = [1, 1, 1, 1]
Output: [1, 1, 1, 1]
Explanation: Every node has value 1, so no nodes are removed.
``````

Constraints:

``````- The number of the nodes in the given list is in the range [1, 10^5].
- 1 <= Node.val <= 10^5
``````

### Explanation

#### Brute Force

The easiest approach is to run two loops. The outer loop picks one node at a time. The inner loop check if there exists a node greater than the current node. If it exists, we delete the current node.

The time-complexity of the above approach is O(n^2), and the space complexity is O(1).

#### Using Reverse

The time-complexity can be reduced to O(n) by reversing the linked list.

The algorithm looks as below:

``````// reverse linked list method
- set ListNode* previous = null

- loop while current != null
- set temp = current->next
current->next = previous
previous = current
current = temp
- loop end

- return previous

// removeNodes method

- set ListNode* current = reverse(head)
int val = current->val

- loop while current != null && current->next != null
- loop while current != null && current->next != null && current->next->val < val
- set current->next = current->next->next
- while end

- if current != null && current->next != null
- set val = max(val, current->next->val)
current = current->next
- if end
- while end

``````

The time-complexity of the above approach is O(n), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
ListNode* previous = NULL;

while(current != NULL){
ListNode* temp = current->next;
current->next = previous;
previous = current;
current = temp;
}

return previous;
}

}

int val = current->val;

while(current != NULL && current->next != NULL){
while(current != NULL && current->next != NULL && current->next->val < val){
current->next = current->next->next;
}

if(current != NULL && current->next != NULL){
val = max(val, current->next->val);
current = current->next;
}

}

}
};``````

#### Golang solution

``````func max(a, b int) int {
if a > b {
return a
}

return b
}

var previous *ListNode

for current != nil {
temp := current.Next
current.Next = previous
previous = current
current = temp
}

return previous
}

}

val := current.Val

for current != nil && current.Next != nil {
for current != nil && current.Next != nil && current.Next.Val < val {
current.Next = current.Next.Next
}

if current != nil && current.Next != nil {
val = max(val, current.Next.Val)
current = current.Next
}
}

}``````

#### Javascript solution

``````var reverse = function(head) {
let previous = null;

while(current) {
let temp = current.next;
current.next = previous;
previous = current;
current = temp;
}

return previous;
};

}

let val = current.val;

while(current != null && current.next != null) {
while(current != null && current.next != null && current.next.val < val){
current.next = current.next.next;
}

if(current != null && current.next != null){
val = Math.max(val, current.next.val);
current = current.next;
}
}

};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: head = [5, 2, 13, 3, 8]

false

Step 2: ListNode* current = reverse(head)

reverse will return the linked list as [8, 3, 13, 2, 5]
current = 8

= 8

int val = current->val
= 8

Step 3: loop while current != NULL && current->next != NULL
8 != NULL && 8->next != NULL
8 != NULL && 3 != NULL
true

loop while current != NULL && current->next != NULL && current->next->val < val
8 != NULL && 8->next != NULL && 8->next->val < 8
8 != NULL && 3 != NULL && 3 < 8
true

current->next = current->next->next
8->next = 8->next->next
8->next = 3->next
= 13

The updated linked list is [8, 13, 2, 5]

loop while current != NULL && current->next != NULL && current->next->val < val
8 != NULL && 8->next != NULL && 8->next->val < 8
8 != NULL && 13 != NULL && 13 < 8
false

if current != NULL && current->next != NULL
8 != NULL && 13 != NULL
true

val = max(val, current->next->val)
= max(8, 8->next->val)
= max(8, 13)
= 13

current = current->next
= 8->next
= 13

Step 4: loop while current != NULL && current->next != NULL
13 != NULL && 13->next != NULL
13 != NULL && 2 != NULL
true

loop while current != NULL && current->next != NULL && current->next->val < val
13 != NULL && 13->next != NULL && 13->next->val < 13
13 != NULL && 2 != NULL && 2 < 8
true

current->next = current->next->next
13->next = 13->next->next
13->next = 13->next
= 2

The updated linked list is [8, 13, 5]

loop while current != NULL && current->next != NULL && current->next->val < val
13 != NULL && 13->next != NULL && 13->next->val < 13
13 != NULL && 5 != NULL && 5 < 8
true

current->next = current->next->next
13->next = 13->next->next
13->next = 5->next
= NULL

The updated linked list is [8, 13]

loop while current != NULL && current->next != NULL && current->next->val < val
13 != NULL && 13->next != NULL
13 != NULL && NULL != NULL
false

if current != NULL && current->next != NULL
13 != NULL && 13->next != NULL
13 != NULL && NULL != NULL
false

Step 5: loop while current != NULL && current->next != NULL
13 != NULL && 13->next != NULL
13 != NULL && NULL != NULL
false