Leetcode -817.链表组件
题目：给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。
返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。
示例 1：
输入: head = [0, 1, 2, 3], nums = [0, 1, 3]
输出 : 2
解释 : 链表中, 0 和 1 是相连接的，且 nums 中不包含 2，所以[0, 1] 是 nums 的一个组件，同理[3] 也是一个组件，故返回 2。
示例 2：
输入: head = [0, 1, 2, 3, 4], nums = [0, 3, 1, 4]
输出 : 2
解释 : 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以[0, 1] 和[3, 4] 是两个组件，故返回 2。
提示：
链表中节点数为n
1 <= n <= 10^4
0 <= Node.val < n
Node.val 中所有值 不同
1 <= nums.length <= n
0 <= nums[i] < n
nums 中所有值 不同
思路：用hash数组将 nums 数组中出现过的元素记录下来，然后遍历链表，如果可以组成 nums 数组的组件，就用 flag 标记为1，继续判断链表的下一个值是否是nums数组的组件，如果不是，就将上一个链表的组件 flag 统计到 ans 中，最后返回 ans ；如果是，就继续标记 flag 为1，一直迭代链表，直到空；如果一直迭代到空，flag 还是被标记为1，最后要处理这个1，把它统计到 ans 中；
int numComponents(struct ListNode* head, int* nums, int numsSize) { struct ListNode* cur = head; //hash数组记录nums中出现过的元素 int hash[10000] = { 0 }; int flag = 0, ans = 0; //将nums数组中出现过的元素在hash数组中标记为1 for (int i = 0; i < numsSize; i++) { hash[nums[i]] = 1; } while (cur) { //如果链表中的元素有在nums数组中出现过，用flag记录；如果是相连的元素一直出现，那flag也一直等于1，一整串相当于出现一次 if (hash[cur->val]) { flag = 1; } //否则，或者一直出现的元素中断，用ans统计组件的个数；并将flag置0 else { ans += flag; flag = 0; } //cur 迭代 cur = cur->next; } //最后处理被遗漏的flag，因为如果链表中的元素一直连着组成组件，直到链表为空，那么这个组件还没算进 ans ans += flag; return ans; }
Leetcode -1019.链表中的下一个更大节点
题目：给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点(从1开始)的下一个更大的节点的值。
如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0
示例 1：
输入：head = [2, 1, 5]
输出：[5, 5, 0]
示例 2：
输入：head = [2, 7, 4, 3, 5]
输出：[7, 0, 5, 5, 0]
提示：
链表中节点数为 n
1 <= n <= 10^4
1 <= Node.val <= 10^9
思路：暴力方法，直接遍历链表，寻找下一个更大的节点，如果遍历到空，即没有下一个更大的节点，就将 0 放入返回的数组，否则就将这个更大的节点放入返回数组；
int* nextLargerNodes(struct ListNode* head, int* returnSize) { struct ListNode* cur = head, * ptr = head; //用len记录返回的长度，ret为返回的数组 int len = 0; int* ret = (int*)malloc(sizeof(int) * 10000); while (ptr) { //cur每次从ptr开始遍历 cur = ptr; //寻找当前比 ptr 下一个更大节点 //cur的next不能为空，如果ptr的值大于等于cur的next的值，cur往后迭代 while (cur->next && ptr->val >= cur->next->val) cur = cur->next; //如果没找到下一个更大的节点，将0放入返回数组 if (cur->next == NULL) ret[len++] = 0; //如果找到，就将这个节点放入返回数组 else if (ptr->val < cur->next->val) ret[len++] = cur->next->val; //每次找完 ptr 往后迭代 ptr = ptr->next; } *returnSize = len; return ret; }
