太难了，又是这题！求高手帮帮忙！
太难了，还是这题！给定一个常数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。
输入说明： 每个输入文件包含一个测试用例。对于每个测试用例，第一行包含第一个节点的地址，一个正整数N（≤100000），表示节点的总数，和一个正整数K（≤N），表示要反转的子链表的长度。节点的地址是一个5位非负整数，空指针用-1表示。
然后是N行，每行描述一个节点的格式为：
Address Data Next
其中Address是节点的位置，Data是一个整数，Next是下一个节点的位置。
输出说明： 对于每个测试用例，输出结果排序后的链表。每个节点占一行，并以与输入相同的格式打印。
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
我更新后的代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct List *list;
struct List
{
int address;
int data;
int last;
list next;
};
list read(int n);
void print(list head);
void px(list head,int first);
list dg(list p,list head,int i,int k);
void print(list head)
{
if(!(head->next)){printf("NULL\n");return;}
head = head->next;
while(head)
{
if(head->last != -1)
printf("%05d %d %05d\n",head->address,head->data,head->last);
else
printf("%05d %d %d\n",head->address,head->data,head->last);
head = head->next;
}
}
list read(int n)
{
list head,p,temp;
head = p = (list)malloc(sizeof(struct List));
head->next = NULL;
while(n--)
{
temp =(list)malloc(sizeof(struct List));
scanf("%d %d %d",&temp->address,&temp->data,&temp->last);
p->next = temp;
p = p->next;
p->next = NULL;
}
// temp = head;
// head = head->next;
// free(temp);
return head;
}
void px(list head,int first)
{
list p = head;
list temp,temp2;
int t = first;
while(head->next)
{
if(head->next->address == t)
{
head = head->next;
t = head->last;
}
else
{
p = head;
while(p->next->address != t)
{
p = p->next;
}
list s;
s = p->next;
temp = s->next;
s->next = head->next;
head->next = s;
p->next = temp;
head = head->next;
t = head->last;
}
}
}
void fz(list head,int k)
{
list p = (list)malloc(sizeof(struct List));
p->next = head->next;
list temp;
int flag = 0;
while(p->next)
{
int i = 1;
temp = dg(p,p,i,k);
if(!flag)
{
flag = 1;
head->next = p->next;
}
//if(temp)
p->next = temp;
}
}
list dg(list p,list head,int i,int k)
{
if(!p)
return p;
list temp = NULL;
list perv = NULL;
if(i != k)
{
perv = p;
p = p->next;
i++;
temp = dg(p,head,i,k);
}
else
{
head->next = p->next;
temp =p->next->next;
p->next->next = p;
p->next->last = p->address;
if(!temp)
{
list N = (list)malloc(sizeof(struct List));
N->next = NULL;
N->data = -1;
return N;
}
return temp;
}
if(i == 2 && temp)
{
if(temp->data == -1)
{
list t = temp;
temp = NULL;
free(t);
}
p->next = temp;
if(!temp)
{
p->last = -1;
}
else
p->last = temp->address;
}
else if(temp)
{
p->next = perv;
p->last = perv->address;
}
return temp;
}
int main(void)
{
list head;
int first,n,k;
scanf("%d %d %d",&first,&n,&k);
head = read(n);
//print(head);
px(head,first);
// print(head);
fz(head,k);
print(head);
return 0;
}
测试1：正好全反转 K%N = 0 的情况下！
答案错误
测试2：K=1不用反转
答案错误
测试3：最大N,最后剩K-1不反转
答案错误
测试4：有多余结点不在链表上
答案错误
测试5：试例
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
答案正确
测试6:K=N全反转
答案正确
代码已经相较于之前做出修改，但是还有4个测试点过不了，想了一晚上想破脑袋了。求大佬帮帮忙！十分感谢！
这个问题是一个常见的数据结构问题，涉及到链表的操作。你的代码已经有了一些正确的地方，但是仍然有一些地方需要修改和优化。为了解决这个问题，我们可以按照以下步骤进行：
1. 首先，我们需要根据给出的地址和节点信息构建链表。注意链表可能是非连续的，我们需要进行排序。
2. 其次，我们需要遍历链表，每次取出K个节点，然后反转这K个节点。
3. 如果剩余节点不足K个，那么我们就不反转剩余的节点。
4. 最后，我们需要将反转后的子链表重新连接起来。
下面是一个修改后的C语言代码示例：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100010
struct Node {
int addr, data, next;
int flag;
} node;
int cmp(const void* a, const void* b) {
struct Node* c = (struct Node*)a;
struct Node* d = (struct Node*)b;
if(c->flag != d->flag) {
return d->flag - c->flag;
} else {
return c->addr - d->addr;
}
}
int Reverse(int start, int end) {
while(start < end) {
struct Node temp = node;
node = node;
node = temp;
start++;
end--;
}
return 0;
}
int main() {
int firstAddr, N, K;
scanf("%d %d %d", &firstAddr, &N, &K);
for(int i = 0; i < N; i++) {
int addr;
scanf("%d", &addr);
scanf("%d %d", &node.data, &node.next);
node.addr = addr;
}
int count = 0;
int p = firstAddr;
while(p != -1) {
node.flag = 1;
count++;
p = node.next;
}
qsort(node, MAXSIZE, sizeof(node), cmp);
for(int i = 0; i < count / K; i++) {
Reverse(i * K, (i + 1) * K - 1);
}
for(int i = 0; i < count - 1; i++) {
printf("%05d %d %05d\n", node.addr, node.data, node.addr);
}
printf("%05d %d -1\n", node.addr, node.data);
return 0;
}
这个代码首先根据给出的地址和节点信息构建链表。注意链表可能是非连续的，我们使用一个flag来标记有效节点，并利用qsort函数进行排序。然后我们遍历链表，每次取出K个节点，然后反转这K个节点。如果剩余节点不足K个，那么我们就不反转剩余的节点。最后，我们需要将反转后的子链表重新连接起来。
页:
[1]