太难了，又是这题！求高手帮帮忙！

a905448839

太难了，还是这题！

给定一个常数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

我更新后的代码：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. typedef struct List *list;
   
4. struct List
   
5. {
   
6.         int address;
   
7.         int data;
   
8.         int last;
   
9.         list next;
   
10. };
    
11. 
    
12. list read(int n);
    
13. void print(list head);
    
14. void px(list head,int first);
    
15. list dg(list p,list head,int i,int k);
    
16. 
    
17. void print(list head)
    
18. {
    
19.         if(!(head->next)){printf("NULL\n");return;}
    
20.          head = head->next;
    
21.         while(head)
    
22.         {
    
23.                         if(head->last != -1)
    
24.                 printf("%05d %d %05d\n",head->address,head->data,head->last);
    
25.                 else
    
26.                 printf("%05d %d %d\n",head->address,head->data,head->last);
    
27. 
    
28.                 head = head->next;
    
29.         }
    
30. }
    
31. 
    
32. list read(int n)
    
33. {
    
34.         list head,p,temp;
    
35.         head = p = (list)malloc(sizeof(struct List));
    
36.         head->next = NULL;
    
37.         
    
38.         while(n--)
    
39.         {
    
40.                 temp =  (list)malloc(sizeof(struct List));
    
41.                 scanf("%d %d %d",&temp->address,&temp->data,&temp->last);
    
42.                 p->next = temp;
    
43.                 p = p->next;
    
44.                 p->next = NULL;
    
45.         }
    
46.         
    
47. //        temp = head;
    
48. //        head = head->next;
    
49. //        free(temp);
    
50.         
    
51.         return head;
    
52. }
    
53. 
    
54. void px(list head,int first)
    
55. {
    
56.         list p = head;
    
57.         list temp,temp2;
    
58.         int t = first;
    
59.         
    
60.         while(head->next)
    
61.         {
    
62.                 if(head->next->address == t)
    
63.                 {
    
64.                         head = head->next;
    
65.                         t = head->last;
    
66.                 }
    
67.                 else
    
68.                 {
    
69.                         p = head;
    
70.                         while(p->next->address != t)
    
71.                         {
    
72.                                 p = p->next;
    
73.                         }
    
74.                         list s;
    
75.                         s = p->next;
    
76.                         temp = s->next;
    
77.                         s->next = head->next;
    
78.                         head->next = s;
    
79.                         p->next = temp;
    
80.                         head = head->next;
    
81.                         t = head->last;
    
82.                 }
    
83.         }
    
84.         
    
85. }
    
86. 
    
87. void fz(list head,int k)
    
88. {
    
89.         list p = (list)malloc(sizeof(struct List));
    
90.         p->next = head->next;
    
91.         list temp;
    
92.         int flag = 0;
    
93. 
    
94.         while(p->next)
    
95.         {
    
96.                 int i = 1;
    
97.                 temp = dg(p,p,i,k);
    
98.                 if(!flag)
    
99.                 {
    
100.                         flag = 1;
     
101.                         head->next = p->next;
     
102.                                 }
     
103.                                 //if(temp)
     
104.                                 p->next = temp;
     
105.         }
     
106. }
     
107. 
     
108. list dg(list p,list head,int i,int k)
     
109. {
     
110.                 if(!p)
     
111.                 return p;
     
112. 
     
113.         list temp = NULL;
     
114.         list perv = NULL;
     
115.         if(i != k)
     
116.         {
     
117.                 perv = p;
     
118.                 p = p->next;
     
119.                 i++;
     
120.                 temp = dg(p,head,i,k);
     
121.         }
     
122.         else
     
123.         {
     
124.                 head->next = p->next;
     
125.                 temp =  p->next->next;
     
126.                 p->next->next = p;
     
127.                 p->next->last = p->address;
     
128.                 if(!temp)
     
129.                 {
     
130.                         list N = (list)malloc(sizeof(struct List));
     
131.                         N->next = NULL;
     
132.                         N->data = -1;
     
133.                         return N;
     
134.                                 }
     
135.                 return temp;
     
136. 
     
137.         }
     
138.         if(i == 2 && temp)
     
139.                                 {
     
140.                                         if(temp->data == -1)
     
141.                                         {
     
142.                                                 list t = temp;
     
143.                                                 temp = NULL;
     
144.                                                 free(t);
     
145.                                                
     
146.                                         }
     
147.                                         p->next = temp;
     
148.                                         if(!temp)
     
149.                                         {
     
150.                                                 p->last = -1;
     
151.                                         }
     
152.                                         else
     
153.                                         p->last = temp->address;
     
154.                                        
     
155.                                 }               
     
156.         else if(temp)
     
157.                 {
     
158.                         p->next = perv;
     
159.                               p->last = perv->address;
     
160.                                 }
     
161. 
     
162.                
     
163.         return temp;
     
164. }
     
165. 
     
166. int main(void)
     
167. {
     
168.         list head;
     
169.         int first,n,k;
     
170.         scanf("%d %d %d",&first,&n,&k);
     
171.         head = read(n);
     
172.         //print(head);
     
173.         px(head,first);
     
174.        // print(head);
     
175.         fz(head,k);
     
176.        print(head);
     
177. 
     
178.         return 0;
     
179. }

复制代码

测试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个测试点过不了，想了一晚上想破脑袋了。求大佬帮帮忙！十分感谢！

isdkz

这个问题是一个常见的数据结构问题，涉及到链表的操作。你的代码已经有了一些正确的地方，但是仍然有一些地方需要修改和优化。为了解决这个问题，我们可以按照以下步骤进行：

1. 首先，我们需要根据给出的地址和节点信息构建链表。注意链表可能是非连续的，我们需要进行排序。
2. 其次，我们需要遍历链表，每次取出K个节点，然后反转这K个节点。
3. 如果剩余节点不足K个，那么我们就不反转剩余的节点。
4. 最后，我们需要将反转后的子链表重新连接起来。

下面是一个修改后的C语言代码示例：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAXSIZE 100010
   
5. 
   
6. struct Node {
   
7.     int addr, data, next;
   
8.     int flag;
   
9. } node[MAXSIZE];
   
10. 
    
11. int cmp(const void* a, const void* b) {
    
12.     struct Node* c = (struct Node*)a;
    
13.     struct Node* d = (struct Node*)b;
    
14.     if(c->flag != d->flag) {
    
15.         return d->flag - c->flag;
    
16.     } else {
    
17.         return c->addr - d->addr;
    
18.     }
    
19. }
    
20. 
    
21. int Reverse(int start, int end) {
    
22.     while(start < end) {
    
23.         struct Node temp = node[start];
    
24.         node[start] = node[end];
    
25.         node[end] = temp;
    
26.         start++;
    
27.         end--;
    
28.     }
    
29.     return 0;
    
30. }
    
31. 
    
32. int main() {
    
33.     int firstAddr, N, K;
    
34.     scanf("%d %d %d", &firstAddr, &N, &K);
    
35.     for(int i = 0; i < N; i++) {
    
36.         int addr;
    
37.         scanf("%d", &addr);
    
38.         scanf("%d %d", &node[addr].data, &node[addr].next);
    
39.         node[addr].addr = addr;
    
40.     }
    
41.     int count = 0;
    
42.     int p = firstAddr;
    
43.     while(p != -1) {
    
44.         node[p].flag = 1;
    
45.         count++;
    
46.         p = node[p].next;
    
47.     }
    
48.     qsort(node, MAXSIZE, sizeof(node[0]), cmp);
    
49.     for(int i = 0; i < count / K; i++) {
    
50.         Reverse(i * K, (i + 1) * K - 1);
    
51.     }
    
52.     for(int i = 0; i < count - 1; i++) {
    
53.         printf("%05d %d %05d\n", node[i].addr, node[i].data, node[i+1].addr);
    
54.     }
    
55.     printf("%05d %d -1\n", node[count-1].addr, node[count-1].data);
    
56.     return 0;
    
57. }
    

复制代码

这个代码首先根据给出的地址和节点信息构建链表。注意链表可能是非连续的，我们使用一个flag来标记有效节点，并利用qsort函数进行排序。然后我们遍历链表，每次取出K个节点，然后反转这K个节点。如果剩余节点不足K个，那么我们就不反转剩余的节点。最后，我们需要将反转后的子链表重新连接起来。