题目:给你一个链表的头节点 head ,该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。 对于每两个相邻的 0 ,请你将它们之间的所有节点合并成一个节点,其值是所有已合并节点的值之和。然后将所有 0 移除,修改后的链表不应该含有任何 0 。 返回修改后链表的头节点 head 。
示例 1: 输入:head = [0, 3, 1, 0, 4, 5, 2, 0] 输出:[4, 11] 解释: 上图表示输入的链表。修改后的链表包含:
示例 2: 输入:head = [0, 1, 0, 3, 0, 2, 2, 0] 输出:[1, 3, 4] 解释: 上图表示输入的链表。修改后的链表包含:
提示: 列表中的节点数目在范围[3, 2 * 105] 内 0 <= Node.val <= 1000 不 存在连续两个 Node.val == 0 的节点 链表的 开端 和 末尾 节点都满足 Node.val == 0
思路:思路是双指针,一个 prev 指针记录两个零节点之间的和;另外一个 tail 指针一开始从头的 next 开始走,走到下一个零节点停下来,遍历过程中,prev 累加 tail 遍历过的非零节点;当 tail 遍历到零节点,prev 的next 接到 tail ,prev 再到下一个零节点开始,一直循环,直到 tail 为空;当 tail 为空,prev 还没有为空,所以直接将 prev 置空即可;
struct ListNode* mergeNodes(struct ListNode* head)
{
struct ListNode* prev = head, * tail = head->next;
while (tail)
{
//prev 从头开始,因为头节点的 val 等于0,所以 prev 就从头开始记录两个零节点之间的和
//每当 tail 指向 0 的节点,prev的next就接上tail,然后prev往后走,就是到了当前tail的val为 0 的节点,继续记录两个零节点之间的和
if (tail->next && tail->val == 0)
{
prev->next = tail;
prev = prev->next;
}
//如果 tail 还没到零节点,prev的val就累加tail遍历过的节点的val
prev->val += tail->val;
tail = tail->next;
}
//当tail走到空,prev还没到空,将prev的next置空即可
prev->next = NULL;
return head;
}
题目:给你两个整数:m 和 n ,表示矩阵的维数。 另给你一个整数链表的头节点 head 。 请你生成一个大小为 m x n 的螺旋矩阵,矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格,则用 - 1 填充。 返回生成的矩阵。
示例 1: 输入:m = 3, n = 5, head = [3, 0, 2, 6, 8, 1, 7, 9, 4, 2, 5, 5, 0] 输出: [[3, 0, 2, 6, 8], [5, 0, -1, -1, 1], [5, 2, 4, 9, 7]] 解释:上图展示了链表中的整数在矩阵中是如何排布的。 注意,矩阵中剩下的空格用 - 1 填充。
示例 2: 输入:m = 1, n = 4, head = [0, 1, 2] 输出: [[0, 1, 2, -1]] 解释:上图展示了链表中的整数在矩阵中是如何从左到右排布的。 注意,矩阵中剩下的空格用 - 1 填充。
提示: 1 <= m, n <= 105 1 <= m * n <= 105 链表中节点数目在范围[1, m * n] 内 0 <= Node.val <= 1000
思路*:先将矩阵中的元素初始化为 -1 ,使用指针 cur 遍历链表, xi 和 xj 呈顺时针螺旋趋势遍历二维数组,xi 和 xj 每遍历完一行或者一列,需要做相应的操作改变方向继续遍历;
int** spiralMatrix(int m, int n, struct ListNode* head, int* returnSize, int** returnColumnSizes)
{
//返回的二级指针
int** ret = (int**)malloc(sizeof(int*) * m);
//因为返回的列数也是个二维指针,题意是要返回每一行的元素个数,即列数
*returnColumnSizes = (int*)malloc(sizeof(int) * m);
*returnSize = m;
//将二维数组中的值初始化为 -1;并将返回的列数的二维指针的数组填充
for (int i = 0; i < m; i++)
{
ret[i] = (int*)malloc(sizeof(int) * n);
memset(ret[i], -1, sizeof(int) * n);
(*returnColumnSizes)[i] = n;
}
//cur 遍历链表
struct ListNode* cur = head;
for (int i = 0, j = 0; i < m, j < n; i++, j++)
{
//xi 和 xj 呈顺时针螺旋趋势遍历二维数组
int xi = i, xj = j;
//向右
while (xj < n && cur)
{
ret[xi][xj++] = cur->val;
cur = cur->next;
}
xj--; //xj 当前超出列的长度,需要减1
xi++; //从第下一行开始,xi 需要加1
//向下
while (xi < m && cur)
{
ret[xi++][xj] = cur->val;
cur = cur->next;
}
xi--; //xi 当前超出行的长度,需要减1
xj--; //从上一列开始, xj 需要减1
//向左
while (xj > j && cur)
{
ret[xi][xj--] = cur->val;
cur = cur->next;
}
//向上
while (xi > i && cur)
{
ret[xi--][xj] = cur->val;
cur = cur->next;
}
//xi 和 xj 遍历完一圈后,m和n都要减1,因为遍历完相当于二维数组少了一圈
m--;
n--;
}
return ret;
}