add 1019

fishercoder1534 · fishercoder1534 · commit 2b2ae6b8cf4a · 2020-02-15T10:25:52.000-08:00
diff --git a/README.md b/README.md
@@ -113,6 +113,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1022|[Sum of Root To Leaf Binary Numbers](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1022.java) | |Easy|
 |1021|[Remove Outermost Parentheses](https://leetcode.com/problems/remove-outermost-parentheses/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1021.java) | |Easy|
 |1020|[Number of Enclaves](https://leetcode.com/problems/number-of-enclaves/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1020.java) | |Medium|Graph, DFS, BFS, recursion|
+|1019|[Next Greater Node In Linked List](https://leetcode.com/problems/next-greater-node-in-linked-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1019.java) | |Medium|Linked List, Stack|
 |1018|[Binary Prefix Divisible By 5](https://leetcode.com/problems/binary-prefix-divisible-by-5/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1018.java) | |Easy|
 |1014|[Best Sightseeing Pair](https://leetcode.com/problems/best-sightseeing-pair/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1014.java) | |Medium|
 |1013|[Partition Array Into Three Parts With Equal Sum](https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1013.java) | |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_1019.java b/src/main/java/com/fishercoder/solutions/_1019.java
@@ -0,0 +1,66 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.ListNode;
+
+/**
+ * 1019. Next Greater Node In Linked List
+ *
+ * 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].
+ * */
+public class _1019 {
+    public static class Solution1 {
+        public int[] nextLargerNodes(ListNode head) {
+            int len = findLength(head);
+            int[] result = new int[len];
+            ListNode tmp = head;
+            int i = 0;
+            while (tmp != null) {
+                result[i++] = findNextLarger(tmp.val, tmp);
+                tmp = tmp.next;
+            }
+            return result;
+        }
+
+        private int findNextLarger(int val, ListNode head) {
+            ListNode tmp = head.next;
+            while (tmp != null) {
+                if (tmp.val > val) {
+                    return tmp.val;
+                }
+                tmp = tmp.next;
+            }
+            return 0;
+        }
+
+        private int findLength(ListNode head) {
+            ListNode tmp = head;
+            int count = 0;
+            while (tmp != null) {
+                tmp = tmp.next;
+                count++;
+            }
+            return count;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1019Test.java b/src/test/java/com/fishercoder/_1019Test.java
@@ -0,0 +1,37 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.ListNode;
+import com.fishercoder.common.utils.LinkedListUtils;
+import com.fishercoder.solutions._1019;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _1019Test {
+    private static _1019.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1019.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        ListNode head = LinkedListUtils.contructLinkedList(new int[]{2, 1, 5});
+        assertArrayEquals(new int[]{5, 5, 0}, solution1.nextLargerNodes(head));
+    }
+
+    @Test
+    public void test2() {
+        ListNode head = LinkedListUtils.contructLinkedList(new int[]{2, 7, 4, 3, 5});
+        assertArrayEquals(new int[]{7, 0, 5, 5, 0}, solution1.nextLargerNodes(head));
+    }
+
+    @Test
+    public void test3() {
+        ListNode head = LinkedListUtils.contructLinkedList(new int[]{1, 7, 5, 1, 9, 2, 5, 1});
+        assertArrayEquals(new int[]{7, 9, 9, 9, 0, 5, 0, 0}, solution1.nextLargerNodes(head));
+    }
+
+}
