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;
		}