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]
Top comments (0)