Next Greater Node In Linked List (JavaScript)

Question

I'm trying too implement this algorithm in JavaScript.

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:

Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

My solution:

/**
 * 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) {
    let ans = [];
    if(!head)
        return ans;
    
    let p = head;
    while(p) {
        ans.push(getLarger(p.next, p.val));
    }
    
    return ans;
};

const getLarger = function(head, cur) {
    let tmp = cur - 1;
    while(head) {
        tmp = head.val > tmp ? head.val : tmp;
        head = head.next;
    }
    return tmp >= cur ? tmp : 0;
}

When I run this code, I get the following error:

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: 0xa2afd0 node::Abort() [nodejs run]
 2: 0x97a467 node::FatalError(char const*, char const*) [nodejs run]
 3: 0xb9e04e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [nodejs run]
 4: 0xb9e3c7 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [nodejs run]
 5: 0xd3e7d5  [nodejs run]
 6: 0xd50830 v8::internal::Heap::AllocateRawWithRetryOrFailSlowPath(int, v8::internal::AllocationType, v8::internal::AllocationOrigin, v8::internal::AllocationAlignment) [nodejs run]
 7: 0xd24166  [nodejs run]
 8: 0xe840be  [nodejs run]
 9: 0xe87c1a  [nodejs run]
10: 0x1028743 v8::internal::Runtime_GrowArrayElements(int, unsigned long*, v8::internal::Isolate*) [nodejs run]
11: 0x13a9e39  [nodejs run]

while(p) {is an infinite loop since you never change the value of p — Bergi
– Bergi, Commented Jul 15, 2020 at 16:56

Gabriel Nadaleti · Accepted Answer · 2020-07-15 17:02:52Z

1

let p = head;
while(p) {
    ans.push(getLarger(p.next, p.val));
    p = p.next;
}

try changing the value of p

answered Jul 15, 2020 at 17:02

Gabriel Nadaleti

1,7251 gold badge11 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

myTest532 myTest532 Over a year ago

Thank you. I forgot it!

Collectives™ on Stack Overflow

Next Greater Node In Linked List (JavaScript)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related