LeetCode 2487: Remove Nodes From Linked List (Reverse Scan by Right-Side Maximum)
LeetCode 2487Linked ListGreedyToday we solve LeetCode 2487 - Remove Nodes From Linked List.
Source: https://leetcode.com/problems/remove-nodes-from-linked-list/
English
Problem Summary
Given the head of a linked list, remove every node that has a strictly greater value somewhere to its right, and return the remaining list.
Key Insight
A node survives if it is greater than or equal to all nodes on its right. This is easiest when scanning from right to left: keep a running maximum and keep only nodes that meet it.
Algorithm
- Reverse the list.
- Traverse reversed list with maxSoFar.
- Keep node if node.val >= maxSoFar, otherwise skip it.
- Reverse the filtered list back.
Complexity Analysis
Time: O(n).
Space: O(1) extra.
Common Pitfalls
- Using > instead of >=, which wrongly deletes equal-value nodes.
- Forgetting to detach skipped nodes in pointer updates.
- Not reversing back before return.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNodes(ListNode head) {
head = reverse(head);
int maxSoFar = Integer.MIN_VALUE;
ListNode dummy = new ListNode(0), tail = dummy;
while (head != null) {
if (head.val >= maxSoFar) {
maxSoFar = head.val;
tail.next = head;
tail = tail.next;
}
head = head.next;
}
tail.next = null;
return reverse(dummy.next);
}
private ListNode reverse(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNodes(head *ListNode) *ListNode {
head = reverse(head)
maxSoFar := -1 << 60
dummy := &ListNode{}
tail := dummy
for head != nil {
if head.Val >= maxSoFar {
maxSoFar = head.Val
tail.Next = head
tail = tail.Next
}
head = head.Next
}
tail.Next = nil
return reverse(dummy.Next)
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
nxt := cur.Next
cur.Next = prev
prev = cur
cur = nxt
}
return prev
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
head = reverse(head);
int maxSoFar = INT_MIN;
ListNode dummy(0);
ListNode* tail = &dummy;
while (head) {
if (head->val >= maxSoFar) {
maxSoFar = head->val;
tail->next = head;
tail = tail->next;
}
head = head->next;
}
tail->next = nullptr;
return reverse(dummy.next);
}
private:
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(node: Optional[ListNode]) -> Optional[ListNode]:
prev = None
cur = node
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
head = reverse(head)
max_so_far = float('-inf')
dummy = ListNode(0)
tail = dummy
while head:
if head.val >= max_so_far:
max_so_far = head.val
tail.next = head
tail = tail.next
head = head.next
tail.next = None
return reverse(dummy.next)/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var removeNodes = function(head) {
head = reverse(head);
let maxSoFar = -Infinity;
const dummy = new ListNode(0);
let tail = dummy;
while (head) {
if (head.val >= maxSoFar) {
maxSoFar = head.val;
tail.next = head;
tail = tail.next;
}
head = head.next;
}
tail.next = null;
return reverse(dummy.next);
};
function reverse(head) {
let prev = null, cur = head;
while (cur) {
const nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}中文
题目概述
给定链表头结点，删除所有“右侧存在更大值”的节点，返回剩余链表。
核心思路
一个节点能保留，当且仅当它的值大于等于其右侧所有节点。正向不好判断，反向就很直接：维护右侧最大值 maxSoFar。
算法步骤
- 先反转链表。
- 从左到右遍历（等价于原链表从右到左），维护 maxSoFar。
- 若当前值 >= maxSoFar 则保留，否则跳过。
- 将过滤后的链表再反转回来。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1) 额外空间。
常见陷阱
- 把条件写成 >，会错误删除“相等值”节点。
- 跳过节点后忘记正确维护尾指针。
- 最后没反转回原方向。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNodes(ListNode head) {
head = reverse(head);
int maxSoFar = Integer.MIN_VALUE;
ListNode dummy = new ListNode(0), tail = dummy;
while (head != null) {
if (head.val >= maxSoFar) {
maxSoFar = head.val;
tail.next = head;
tail = tail.next;
}
head = head.next;
}
tail.next = null;
return reverse(dummy.next);
}
private ListNode reverse(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNodes(head *ListNode) *ListNode {
head = reverse(head)
maxSoFar := -1 << 60
dummy := &ListNode{}
tail := dummy
for head != nil {
if head.Val >= maxSoFar {
maxSoFar = head.Val
tail.Next = head
tail = tail.Next
}
head = head.Next
}
tail.Next = nil
return reverse(dummy.Next)
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
nxt := cur.Next
cur.Next = prev
prev = cur
cur = nxt
}
return prev
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
head = reverse(head);
int maxSoFar = INT_MIN;
ListNode dummy(0);
ListNode* tail = &dummy;
while (head) {
if (head->val >= maxSoFar) {
maxSoFar = head->val;
tail->next = head;
tail = tail->next;
}
head = head->next;
}
tail->next = nullptr;
return reverse(dummy.next);
}
private:
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(node: Optional[ListNode]) -> Optional[ListNode]:
prev = None
cur = node
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
head = reverse(head)
max_so_far = float('-inf')
dummy = ListNode(0)
tail = dummy
while head:
if head.val >= max_so_far:
max_so_far = head.val
tail.next = head
tail = tail.next
head = head.next
tail.next = None
return reverse(dummy.next)/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var removeNodes = function(head) {
head = reverse(head);
let maxSoFar = -Infinity;
const dummy = new ListNode(0);
let tail = dummy;
while (head) {
if (head.val >= maxSoFar) {
maxSoFar = head.val;
tail.next = head;
tail = tail.next;
}
head = head.next;
}
tail.next = null;
return reverse(dummy.next);
};
function reverse(head) {
let prev = null, cur = head;
while (cur) {
const nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
Comments