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
思路：找到需要交换的两个节点，交换它们的值即可；
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，最大距离即是数组中的最后一个减去第一个，即最大减最小；最小距离需要遍历数组，找到相邻的元素中差值最小的值；
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; }
