aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-25 13:07:56 -0600
committerJack Sangdahl <[email protected]>2025-08-25 13:07:56 -0600
commitf0a4209eaec07cd0eb8bb7ff15be34f8adb1437c (patch)
tree1738e3726b6198e485f10fb26cd8468008915cb8
parent3f521a9849997608712e92ad8e90e83ff1cefdc0 (diff)
downloadleetcode-f0a4209eaec07cd0eb8bb7ff15be34f8adb1437c.tar.gz
leetcode-f0a4209eaec07cd0eb8bb7ff15be34f8adb1437c.zip
1019. next greater node in linked list
-rw-r--r--next_greater_node_link_list.c45
-rw-r--r--next_greater_node_link_list.py35
2 files changed, 80 insertions, 0 deletions
diff --git a/next_greater_node_link_list.c b/next_greater_node_link_list.c
new file mode 100644
index 0000000..3b229a7
--- /dev/null
+++ b/next_greater_node_link_list.c
@@ -0,0 +1,45 @@
+// 1019. Next Greater Node In Linked List
+#include "leetcode.h"
+
+/*
+ * 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 eachnode,
+ * find the value of the first node that is next to it and has a stricty larger
+ * value than it. return an integer array 'answer' where 'answer[i]' is the
+ * value of the next greter node of the i'th node (1-indexed). if the i'th node
+ * does not have a next greater node, set 'ans[i] = 0'.
+ */
+
+int *nextLargerNodes(struct ListNode *head, int *returnSize) {
+ int cnt = 0;
+ struct ListNode *tmp1 = head, *tmp2;
+ for (; tmp1; tmp1 = tmp1->next, cnt++)
+ ;
+ int *ans = (int *)calloc(cnt, sizeof(int));
+ *returnSize = cnt;
+ for (tmp1 = head, cnt = 0; tmp1->next; tmp1 = tmp1->next, cnt++)
+ for (tmp2 = tmp1->next; tmp2; tmp2 = tmp2->next)
+ if (tmp2->val > tmp1->val) {
+ ans[cnt] = tmp2->val;
+ break;
+ }
+ return ans;
+}
+
+int main() {
+ int h1i[] = {2, 1, 5}, h2i[] = {2, 7, 4, 3, 5};
+ struct ListNode *h1 = listnode_build(h1i, ARRAY_SIZE(h1i));
+ struct ListNode *h2 = listnode_build(h2i, ARRAY_SIZE(h2i));
+ int rs1, *nln1 = nextLargerNodes(h1, &rs1);
+ int rs2, *nln2 = nextLargerNodes(h2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", nln1[i]); // expect: 5 5 0
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", nln2[i]); // expect: 7 0 5 5 0
+ printf("\n");
+ free(nln1);
+ free(nln2);
+ listnode_free(h1);
+ listnode_free(h2);
+}
diff --git a/next_greater_node_link_list.py b/next_greater_node_link_list.py
new file mode 100644
index 0000000..70d9d79
--- /dev/null
+++ b/next_greater_node_link_list.py
@@ -0,0 +1,35 @@
+# 1019. Next Greater Node In Linked List
+from leetcode import listnode_build
+
+"""
+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 eachnode,
+find the value of the first node that is next to it and has a stricty larger
+value than it. return an integer array 'answer' where 'answer[i]' is the
+value of the next greter node of the i'th node (1-indexed). if the i'th node
+does not have a next greater node, set 'ans[i] = 0'.
+"""
+
+
+class Solution(object):
+ def nextLargerNodes(self, head):
+ """
+ :type head: Optional[ListNode]
+ :rtype: List[int]
+ """
+ ans, stack = [], []
+ while head:
+ while stack and stack[-1][1] < head.val:
+ ans[stack.pop()[0]] = head.val
+ stack.append([len(ans), head.val])
+ ans.append(0)
+ head = head.next
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ h1 = listnode_build(vals=[2, 1, 5])
+ h2 = listnode_build(vals=[2, 7, 4, 3, 5])
+ print(obj.nextLargerNodes(h1))
+ print(obj.nextLargerNodes(h2))