Leetcode 2487. Remove Nodes From Linked List

[Woodyiiiiiii]

这道题是很简单的链表题。之前好久没做链表题了，看来有点生疏了。

难点在于如何提前知道一个节点右侧是否有严格大于它的节点。这里我一开始想要用堆或者哈希表来做，但没有走通。

仔细想想，我不需要知道大于该节点数值的值及位置，所以：

• 预处理，从右往左遍历
• 记录每次的最大值，从而知道是否有无严格大的值

需要消耗O(n)的空间，不然无法倒序遍历。

注意下就行。算是醒脑复习。

/**
 * 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) {
        ListNode pre = new ListNode(-1);
        List<Integer> list = new ArrayList<>();

        ListNode node = head;
        while (node != null) {
            list.add(node.val);
            node = node.next;
        }

        // dp[i] = 1 means there is a greater element in the right of i, otherwise 0
        int[] dp = new int[list.size()];
        int rightMax = 0;
        for (int i = list.size() - 1; i >= 0; --i) {
            dp[i] = list.get(i) < rightMax ? 1 : 0;
            rightMax = Math.max(rightMax, list.get(i));
        }

        node = head;
        int i = 0;
        ListNode newEnd = pre;
        while (node != null) {
            if (dp[i] == 0) {
                ListNode newNode = new ListNode(list.get(i));
                if (newEnd == pre) {
                    newEnd.next = newNode;
                } else {
                    newEnd.next = newNode;
                }
                newEnd = newEnd.next;
            }
            node = node.next;
            ++i;
        }

        return pre.next;
    }
}

---

• https://leetcode.com/problems/remove-nodes-from-linked-list/