[코테연습] 2487. Remove Nodes From Linked List

- LinkedList Node 문제

 

https://leetcode.com/problems/remove-nodes-from-linked-list/description/?envType=daily-question&envId=2024-05-06

 

- 문제분석

1. ListNode 를 나열 했을 때, 왼쪽보다 오른쪽이 더 큰 경우에는 왼쪽 node 를 모두 삭제한다.

2. [5,2,13,3,8] 일 경우 13보다 작은 5,2 node 를 삭제하고, 8보다 작은 3 node 를 삭제한다.

 

- 문제풀이

1. ListNode의 value 값을 모두 while 반복문으로 확인하고, List<Integer> list 에 넣는다.

2. list 를 역순으로 다시 for 반복문을 돌린다.

3. 숫자에서 가장 큰숫자를 max 값으로 저장해두고, 현재 숫자가 max보다 큰경우 stack에 저장한다.

4. stack에 저장된 숫자를 재귀문으로 ListNode 로 만든다.

 

class Solution {
    public ListNode removeNodes(ListNode head) {
        
        ListNode node = head;

        List<Integer> list = new ArrayList<>();
        while(node != null) {
            list.add(node.val);
            node = node.next;
        }

        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = list.size()-1; i >= 0; i--) {
            int num = list.get(i);
            max = Math.max(max, num);

            if (num >= max) {
                stack.push(num);
            }
        }


        ListNode newNode = new ListNode();
        make(newNode,stack);
      
        return newNode.next;
    }

    void make(ListNode root, Stack<Integer> stack){
        if (!stack.isEmpty()) {
            root.next = new ListNode(stack.pop());
            make(root.next, stack);
        }
    }
}