题目:给你链表的头节点 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;
}
题目:链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。 如果当前节点的值 严格大于 前一个节点和后一个节点,那么这个节点就是一个 局部极大值点 。 如果当前节点的值 严格小于 前一个节点和后一个节点,那么这个节点就是一个 局部极小值点 。 注意:节点只有在同时存在前一个节点和后一个节点的情况下,才能成为一个 局部极大值点 / 极小值点 。 给你一个链表 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] 解释:存在三个临界点:
示例 3: 输入:head = [1, 3, 2, 2, 3, 2, 2, 2, 7] 输出:[3, 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;
}