Tìm nút lớn hơn tiếp theo cho mỗi nút trong JavaScript

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy phần đầu của danh sách liên kết làm đối số đầu tiên và duy nhất.

Danh sách liên kết này chứa dữ liệu số. Mỗi nút trong danh sách có thể có giá trị lớn hơn tiếp theo:đối với node_i, next_larger (node_i) là node_j.val sao cho j> i, node_j.val> node_i.val và j là lựa chọn nhỏ nhất có thể. Nếu j như vậy không tồn tại, giá trị lớn hơn tiếp theo là 0.

Hàm của chúng ta sẽ chuẩn bị và trả về một mảng trong đó phần tử tương ứng là phần tử lớn hơn tiếp theo cho phần tử trong danh sách.

Ví dụ:nếu danh sách -

Sau đó, đầu ra phải là -

const output = [7, 0, 5, 5, 0];

Giải thích đầu ra:

Vì phần tử lớn hơn tiếp theo của 2 là 7 nên đối với 7 không có phần tử nào lớn hơn, v.v.

Ví dụ

Mã cho điều này sẽ là -

class Node{
   constructor(data){
      this.data = data;
      this.next = null;
   };
};
class LinkedList{
   constructor(){
      this.head = null;
      this.size = 0;
   };
};
LinkedList.prototype.add = function(data){
   const newNode = new Node(data);
   let curr
   if(this.head === null){
      this.head = newNode;
   }else{
      curr = this.head;
      while (curr.next) {
         curr = curr.next;
      }
      curr.next = newNode;
   };
   this.size++;
};
const list = new LinkedList();
list.add(2);
list.add(7);
list.add(4);
list.add(3);
list.add(5);
const nextGreater = (head) => {
   const arr = [];
   const res = [];
   let curr = head;
   let currentIndex = 0
   while(curr){
      while (arr.length > 0 && curr.data > arr[arr.length - 1][1]) {
         const [index] = arr.pop();
         res[index] = curr.data;
      };
      arr.push([currentIndex, curr.data]);
      currentIndex += 1;
      curr = curr.next;
   };
   for(let i = 0; i < currentIndex; i++){
      if(res[i] === undefined){
         res[i] = 0;
      };
   };
   return res;
};
console.log(nextGreater(list.head));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

[ 7, 0, 5, 5, 0 ]