Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Move from brute-force thinking to an efficient approach using linked list strategy.
You are given the head of a linked list.
Remove every node which has a node with a 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:
[1, 105].1 <= Node.val <= 105Problem summary: You are given the head of a linked list. Remove every node which has a node with a greater value anywhere to the right side of it. Return the head of the modified linked list.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Linked List · Stack
[5,2,13,3,8]
[1,1,1,1]
reverse-linked-list)delete-node-in-a-linked-list)next-greater-element-i)delete-nodes-from-linked-list-present-in-array)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2487: Remove Nodes From Linked List
/**
* 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) {
List<Integer> nums = new ArrayList<>();
while (head != null) {
nums.add(head.val);
head = head.next;
}
Deque<Integer> stk = new ArrayDeque<>();
for (int v : nums) {
while (!stk.isEmpty() && stk.peekLast() < v) {
stk.pollLast();
}
stk.offerLast(v);
}
ListNode dummy = new ListNode();
head = dummy;
while (!stk.isEmpty()) {
head.next = new ListNode(stk.pollFirst());
head = head.next;
}
return dummy.next;
}
}
// Accepted solution for LeetCode #2487: Remove Nodes From Linked List
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNodes(head *ListNode) *ListNode {
nums := []int{}
for head != nil {
nums = append(nums, head.Val)
head = head.Next
}
stk := []int{}
for _, v := range nums {
for len(stk) > 0 && stk[len(stk)-1] < v {
stk = stk[:len(stk)-1]
}
stk = append(stk, v)
}
dummy := &ListNode{}
head = dummy
for _, v := range stk {
head.Next = &ListNode{Val: v}
head = head.Next
}
return dummy.Next
}
# Accepted solution for LeetCode #2487: Remove Nodes From Linked List
# 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]:
nums = []
while head:
nums.append(head.val)
head = head.next
stk = []
for v in nums:
while stk and stk[-1] < v:
stk.pop()
stk.append(v)
dummy = ListNode()
head = dummy
for v in stk:
head.next = ListNode(v)
head = head.next
return dummy.next
// Accepted solution for LeetCode #2487: Remove Nodes From Linked List
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2487: Remove Nodes From Linked List
// /**
// * 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) {
// List<Integer> nums = new ArrayList<>();
// while (head != null) {
// nums.add(head.val);
// head = head.next;
// }
// Deque<Integer> stk = new ArrayDeque<>();
// for (int v : nums) {
// while (!stk.isEmpty() && stk.peekLast() < v) {
// stk.pollLast();
// }
// stk.offerLast(v);
// }
// ListNode dummy = new ListNode();
// head = dummy;
// while (!stk.isEmpty()) {
// head.next = new ListNode(stk.pollFirst());
// head = head.next;
// }
// return dummy.next;
// }
// }
// Accepted solution for LeetCode #2487: Remove Nodes From Linked List
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeNodes(head: ListNode | null): ListNode | null {
const nums = [];
for (; head; head = head.next) {
nums.push(head.val);
}
const stk: number[] = [];
for (const v of nums) {
while (stk.length && stk.at(-1)! < v) {
stk.pop();
}
stk.push(v);
}
const dummy = new ListNode();
head = dummy;
for (const v of stk) {
head.next = new ListNode(v);
head = head.next;
}
return dummy.next;
}
Use this to step through a reusable interview workflow for this problem.
Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.
Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.