2573. Remove Nodes From Linked List¶

Difficulty: Medium

2573. Remove Nodes From Linked List

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.

Constraints:

The number of the nodes in the given list is in the range [1, 10⁵].
1 <= Node.val <= 10⁵

Solution¶

/**
 * 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) {
        ArrayList<Integer> arr = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            arr.add(temp.val);
            temp = temp.next;
        }
        int next_greater[] = new int[arr.size()];
        Stack<Integer> st = new Stack<>();
        for (int i = arr.size() - 1; i >= 0; i--) {
            while (st.size() > 0 && st.peek() <= arr.get(i)) st.pop();
            if (st.size() > 0) next_greater[i] = st.peek();
            else next_greater[i] = -1;
            st.add(arr.get(i));
        }
        ListNode res = null;
        for (int i = arr.size() - 1; i >= 0; i--) {
            if (next_greater[i] == -1) {
                res = insert(res, arr.get(i));
            }
        }
        return res;
    }

    private ListNode insert(ListNode head, int data) {
        ListNode to_insert = new ListNode(data);
        if (head == null) return new ListNode(data);
        to_insert.next = head;
        head = to_insert;
        return head;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here