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 中；
代码语言：javascript复制 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 放入返回的数组，否则就将这个更大的节点放入返回数组；
代码语言：javascript复制 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;
}
