Leetcode -1721.交换链表中的节点
题目：给你链表的头节点 head 和一个整数 k 。 交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
示例 1： 输入：head = [1, 2, 3, 4, 5], k = 2 输出：[1, 4, 3, 2, 5]
示例 2： 输入：head = [7, 9, 6, 6, 7, 8, 3, 0, 9, 5], k = 5 输出：[7, 9, 6, 6, 8, 7, 3, 0, 9, 5]
示例 3： 输入：head = [1], k = 1 输出：[1]
示例 4： 输入：head = [1, 2], k = 1 输出：[2, 1]
示例 5： 输入：head = [1, 2, 3], k = 2 输出：[1, 2, 3]
提示： 链表中节点的数目是 n 1 <= k <= n <= 105 0 <= Node.val <= 100
思路：找到需要交换的两个节点，交换它们的值即可；
代码语言：javascript复制 struct ListNode* swapNodes(struct ListNode* head, int k)
{
//front为交换的两个节点的前一个节点，behind为交换的两个节点的后一个节点，cur用来让两个节点找到交换的两个位置
struct ListNode* front = head, * behind = head, * cur = head;
//front找到交换的第一个节点
while (--k)
{
front = front->next;
cur = cur->next;
}
//behind找到交换的第二个节点
while (cur->next)
{
cur = cur->next;
behind = behind->next;
}
//找到两个交换的节点之后，就对它们进行换值
int num = front->val;
front->val = behind->val;
behind->val = num;
return head;
}Leetcode -2058.找出临界点之间的最小和最大距离
题目：链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。 如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。 如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。 注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。 给你一个链表 head ，返回一个长度为 2 的数组[minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回[-1， - 1] 。
示例 1： 输入：head = [3, 1] 输出：[-1, -1] 解释：链表[3, 1] 中不存在临界点。
示例 2： 输入：head = [5, 3, 1, 2, 5, 1, 2] 输出：[1, 3] 解释：存在三个临界点：
- [5, 3, 1, 2, 5, 1, 2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。
- [5, 3, 1, 2, 5, 1, 2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。
- [5, 3, 1, 2, 5, 1, 2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。 第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。 第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。
示例 3： 输入：head = [1, 3, 2, 2, 3, 2, 2, 2, 7] 输出：[3, 3] 解释：存在两个临界点：
- [1, 3, 2, 2, 3, 2, 2, 2, 7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。
- [1, 3, 2, 2, 3, 2, 2, 2, 7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。 最小和最大距离都存在于第二个节点和第五个节点之间。 因此，minDistance 和 maxDistance 是 5 - 2 = 3 。 注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。
示例 4： 输入：head = [2, 3, 3, 2] 输出：[-1, -1] 解释：链表[2, 3, 3, 2] 中不存在临界点。
提示： 链表中节点的数量在范围[2, 105] 内 1 <= Node.val <= 105
思路：遍历链表，找到链表中所有的临界点，放入提前创建好的数组中；然后判断临界点的数量是否大于2，如果小于2，即返回的数组中的最小距离和最大距离都是 -1 ；如果大于2，最大距离即是数组中的最后一个减去第一个，即最大减最小；最小距离需要遍历数组，找到相邻的元素中差值最小的值；
代码语言：javascript复制 int* nodesBetweenCriticalPoints(struct ListNode* head, int* returnSize)
{
struct ListNode* cur = head;
//minDistance为最小距离，maxDistance为最大距离，index记录下标
int minDistance = -1, maxDistance = -1, index = 1;
//返回两个整型
int* ret = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
//数组存放临界点的下标，len记录当前数组的长度
int arr[100000] = { 0 };
int len = 0;
//每次比较前一个的val和后一个val，若符合题意就放入数组
while (cur->next && cur->next->next)
{
int x = cur->val;
cur = cur->next;
index ;
if (cur->val > x && cur->val > cur->next->val)
arr[len ] = index;
else if (cur->val < x&& cur->val < cur->next->val)
arr[len ] = index;
}
//len，数组长度大于1，据题意，即临界点要大于两个
if (len > 1)
{
//上面len多加了一次，所以要减一次
len--;
//maxDistance即为最大减最小
maxDistance = abs(arr[len] - arr[0]);
//minDistance要遍历一次数组，找出相邻之间最小的值
for (int i = 1; i <= len; i )
{
if (i == 1)
minDistance = arr[i] - arr[i - 1];
minDistance = minDistance > arr[i] - arr[i - 1] ? arr[i] - arr[i - 1] : minDistance;
}
}
ret[0] = minDistance;
ret[1] = maxDistance;
return ret;
}
