[LeetCode] 2487. Remove Nodes From Linked List

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

leetcode - 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.

 

연결리스트의 head가 주어진다.

노드의 다음 노드들 중 더 큰 값이 있다면, 그 노드를 삭제하라.

모든 작업이 끝나고 나서의 연결 리스트를 반환하시오.

 

풀이

1. 스택을 이용한 풀이

모든 노드를 순차적으로 읽으면서, 스택에 넣는다. 동시에 모든 의존성을 끊어준다.

스택에 있는 노드들을 꺼내면서, 그 노드가 새 연결리스트의 head보다 크거나 같으면 그 노드를 새 연결리스트의 새 head로 한다.

 

2. 재귀를 이용한 풀이

만약 현재 노드가 NULL이라면, NULL을 반환한다.

만약 다음 노드가 NULL이라면, 현재 head를 반환한다.

만약 다음 노드의 값이 더 크다면, 다음 노드를 반환한다. 다음 노드는 재귀 호출을 통해 미리 구해놓는다.

 

코드

C++ - 스택을 이용한 풀이

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        stack<ListNode*> st;
        ListNode* node = head;
        while(head != nullptr) {
            st.push(head);
            node = head;
            head = head -> next;
            node -> next = nullptr;
        }

        head = st.top();
        st.pop();

        while(!st.empty()) {
            if(head -> val <= st.top() -> val) {
                node = st.top();
                node -> next = head;
                head = node;
            }
            st.pop();
        }
        
        return head;
    }
};

 

 

C++ - 재귀를 이용한 풀이

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        if(head == NULL) return NULL;
        head -> next = removeNodes(head -> next);
        if(head -> next == NULL) return head;
        if(head -> next -> val > head -> val) {
            return head -> next;
        }
        return head;
    }
};