[Leetcode] 1019. Next Greater Node In Linked List

문제

You are given the head of a linked list with n nodes.

For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.

Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If the ith node does not have a next greater node, set answer[i] = 0.

Example 1:

Input: head = [2,1,5]
Output: [5,5,0]

Example 2:

Input: head = [2,7,4,3,5]
Output: [7,0,5,5,0]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 104
• 1 <= Node.val <= 109

풀이

힌트와 같이 스택을 사용하는 것이 이 문제의 키포인트이다.

같이 뒤의 element부터 reverse for loop으로 stack의 가장 첫 숫자를 비교하면서 replace하고 stack에 넣으면 된다. 

reverse for loop은 singly linked list인 상태에서는 불가능하니 따로 array를 만들어 사용한다.

 

 

코드

#define MAX_LIST 10001
int* nextLargerNodes(struct ListNode* head, int* returnSize) {
    
    int stack[MAX_LIST] = {0};
    int top = -1;
    
    int* result = (int*)malloc(MAX_LIST * sizeof(int));
    *returnSize = 0;
    
    struct ListNode* curr = head;
    while(curr) {
        result[(*returnSize)++] = curr->val;
        curr = curr->next;
    }
    
    for(int i=(*returnSize)-1; i>=0; i--) {
        int temp = result[i];
        while(top > -1 && stack[top] <= result[i]) {
            top--;
        }
        if(top == -1)  result[i] = 0;
        else result[i] = stack[top];
        
        stack[++top] = temp;
        
    }
    return result;
}

* 이 포스트는 기록용 입니다.