PAT (Basic Level) Practice 1025 反转链表分数 25

给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6 4

00000 4 99999

00100 1 12309

68237 6 -1

33218 3 00000

99999 5 68237

12309 2 33218

输出样例：

00000 4 33218

33218 3 12309

12309 2 00100

00100 1 99999

99999 5 68237

68237 6 -1

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

解题：

#include<stdio.h>

#include<stdlib.h>

typedef struct

{

int address;

int num;

int next;

}Node;

int main()

{

int i, j, n, m, k, roll, next;

Node *node, tmp;

scanf("%d%d%d", &next, &n, &k);

node = (Node*)malloc(sizeof(Node) * n);

for (i = 0; i < n; i++)

{

scanf("%d%d%d", &node[i].address, &node[i].num, &node[i].next);

}

for (i = 0; i < n; i++)

{

for (j = i; j < n; j++)

{

if (node[j].address == next)

{

tmp = node[i];

node[i] = node[j];

node[j] = tmp;

next = node[i].next;

if (node[i].next == -1)

{

n = i + 1;

}

break;

}

}

}//先按链表顺序排序

roll = n / k;

for (j = 0; j < roll; j++)

{

for (m = k - 1, i = j * k; i - j * k < k / 2; i++, m--)

{

tmp = node[i];

node[i] = node[m + j * k];

node[m + j * k] = tmp;

}

}//反转链表

node[n - 1].next = -1;

for (i = n - 1; i > 0; i--)

{

node[i - 1].next = node[i].address;

}//修改链表的后继地址指针

for (i = 0; i < n; i++)

{

if (i == n - 1)

{

printf("%05d %d %d\n", node[i].address, node[i].num, node[i].next);

break;

}

printf("%05d %d %05d\n", node[i].address, node[i].num, node[i].next);

}//按链表顺序输出链表

system("pause");//暂停黑窗口查看结果；

return 0;

}

巴特西

PAT (Basic Level) Practice 1025 反转链表分数 25

输入格式：

输出格式：

输入样例：

输出样例：

解题：

最新文章

热门文章

巴特西

PAT (Basic Level) Practice 1025 反转链表 分数 25

输入格式：

输出格式：

输入样例：

输出样例：

解题：

最新文章

热门文章

PAT (Basic Level) Practice 1025 反转链表分数 25