/
NextGreaterNodeInLinkedListRecursion.js
80 lines (75 loc) · 2.11 KB
/
NextGreaterNodeInLinkedListRecursion.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Source : https://leetcode.com/problems/next-greater-node-in-linked-list/
// Author : Dean Shi
// Date : 2020-10-03
/***************************************************************************************
* We are given a linked list with head as the first node. Let's number the nodes in
* the list: node_1, node_2, node_3, ... etc.
*
* Each node may have a next larger value: for node_i, next_larger(node_i) is the
* node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible
* choice. If such a j does not exist, the next larger value is 0.
*
* Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).
*
* Note that in the example inputs (not outputs) below, arrays such as [2,1,5]
* represent the serialization of a linked list with a head node value of 2, second
* node value of 1, and third node value of 5.
*
* Example 1:
*
* Input: [2,1,5]
* Output: [5,5,0]
*
* Example 2:
*
* Input: [2,7,4,3,5]
* Output: [7,0,5,5,0]
*
* Example 3:
*
* Input: [1,7,5,1,9,2,5,1]
* Output: [7,9,9,9,0,5,0,0]
*
* Note:
*
* 1 <= node.val <= 10^9 for each node in the linked list.
* The given list has length in the range [0, 10000].
*
*
***************************************************************************************/
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var nextLargerNodes = function(head) {
if (!head.next) {
head.largest = head.val
return [0]
}
const result = nextLargerNodes(head.next)
head.largest = head.next.largest
let currNum
if (head.next.val > head.val) {
currNum = head.next.val
} else {
if (head.val >= head.largest) {
currNum = 0
head.largest = head.val
} else {
currNum = getNextLargeNum(head.val, result)
}
}
result.unshift(currNum)
return result
};
function getNextLargeNum(num, arr) {
for (let n of arr) if (num < n) return n
return 0
}