## DEV Community

Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

# 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.

Problem statement taken from: https://leetcode.com/problems/remove-nodes-from-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
ListNode* current = head

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

- return previous

// removeNodes method
- if head == null || head->next == null
- return head

- set ListNode* current = reverse(head)
ListNode* answer = current
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

- return reverse(answer)
``````

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* reverse(ListNode* head){
ListNode* previous = NULL;
ListNode* current = head;

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

return previous;
}

ListNode* removeNodes(ListNode* head) {
if(head == NULL || head->next == NULL) {
return head;
}

ListNode* current = reverse(head);
ListNode* answer = current;

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;
}

}

return reverse(answer);
}
};
``````

#### Golang solution

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

return b
}

func reverse(head *ListNode) *ListNode {
var previous *ListNode
current := head

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

return previous
}

func removeNodes(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}

current := reverse(head)
answer := current

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
}
}

return reverse(answer)
}
``````

#### Javascript solution

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

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

return previous;
};

var removeNodes = function(head) {
if(head == null || head.next == null) {
return head;
}

let current = reverse(head);
let answer = current;

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;
}
}

return reverse(answer);
};
``````

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

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

Step 1: if head == NULL || head->next == NULL
head = 5
false

Step 2: ListNode* current = reverse(head)

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

ListNode* answer = current
= 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

Step 6: return reverse(answer)
reverse(answer)
= [13, 8]
``````