LeetCode 2487: Remove Nodes From Linked List
Problem Description
Explanation
To solve this problem, we can iterate through the linked list in reverse order while keeping track of the maximum value encountered so far. If we find a node with a value greater than the current maximum, we remove that node from the list. Finally, we reverse the modified linked list to get the correct order.
- Start by iterating through the linked list in reverse order.
- Keep track of the maximum value encountered so far.
- If a node's value is greater than the current maximum, remove that node.
- Reverse the modified linked list to get the final result.
Time Complexity: O(N) where N is the number of nodes in the linked list. Space Complexity: O(1)
Solutions
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public ListNode removeNodesFromList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode current = head;
ListNode prev = dummy;
int max = Integer.MIN_VALUE;
while (current != null) {
if (current.val > max) {
max = current.val;
prev = current;
} else {
prev.next = current.next;
}
current = current.next;
}
return reverseList(dummy.next);
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}Loading editor...