首頁 解題筆記 Leetcode Medium

⭐️⭐️⭐️

# 題目敘述

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 內容

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




單字
** **
!! !!
片語 & 搭配詞
!! !!