diff options
author | Jack Sangdahl <[email protected]> | 2025-08-25 13:07:56 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-25 13:07:56 -0600 |
commit | f0a4209eaec07cd0eb8bb7ff15be34f8adb1437c (patch) | |
tree | 1738e3726b6198e485f10fb26cd8468008915cb8 | |
parent | 3f521a9849997608712e92ad8e90e83ff1cefdc0 (diff) | |
download | leetcode-f0a4209eaec07cd0eb8bb7ff15be34f8adb1437c.tar.gz leetcode-f0a4209eaec07cd0eb8bb7ff15be34f8adb1437c.zip |
1019. next greater node in linked list
-rw-r--r-- | next_greater_node_link_list.c | 45 | ||||
-rw-r--r-- | next_greater_node_link_list.py | 35 |
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)) |