2487. Remove Nodes From Linked List

⭐⭐⭐

題目敘述

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.

ListNode 的 class 內容

// 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; }
}

解題思路

Solution

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public ListNode removeNodes(ListNode head) {
        ListNode curr = head;
        Deque<Integer> dq = new ArrayDeque<>();
        
        while (curr != null) {
            while(dq.size() > 0 && dq.peekLast() < curr.val) {
                dq.pollLast();
            }
            dq.add(curr.val);
            curr = curr.next;
        }

        ListNode ans = new ListNode();
        ListNode temp = ans;

        while (!dq.isEmpty()) {
            temp.next = new ListNode(dq.pollFirst());
            temp = temp.next;
        }

        return ans.next;
    }
}