前言

在准备考研复习专业课数据结构,所以我在mooc平台上找了浙江大学的数据结构课程重新学习,感觉老师留的课后题都很有趣,所以想记录下自己的学习过程。

题目:

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

1
Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

1
2
3
4
5
6
7
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

1
2
3
4
5
6
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

先秀一下AC的图,嘿嘿

题解

题目大意

​ 这道题目的大概意思是要求将一个长度为N的链表每k个元素的位置反转过来。

例如 链表为 1→2→3→4→5→6 当k为3时,反转后的链表就应该为3→2→1→6→5→4;当k为4时,反转后的链表就应该为4→3→2→1→5→6。

题目分析

不过离谱的是,这题目又不直接给个链表,而是给结点的地址、值和下一个结点的地址(难道出题老师是为了考虑其他不用c或者c++的同学?),所以要解这个题,我们要先建立链表(有的同学想把数据直接全存数组中,然后排好序之后输出;可是老师也想到了这种投机取巧的方法,于是测试数据中增加了不在链表上的结点)。

建立链表之前肯定得把之前的结点都存起来,然后才能建立链表。所以很自然的就想出要有两个结构体,一个是保存结点的数据,另一个自然是链表了。

1
2
3
4
5
6
7
8
9
10
11
typedef struct Node{
int address;
int data;
int next;
}Node;
Node List[100000];//因为给的地址是5位数的,所以我们要创建一个100000大小的数组来存储它
typedef struct point{
int address;
int data;
point *next;
}point,*Link;

有了结构体,我们自然要读取结点然后创建链表了,这都是常规操作故不详细说明。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int k,n,head,address;
scanf("%d%d%d",&head,&n,&k);

Link q,true_list,r;
q = true_list = (Link)malloc(sizeof(point));
q->next = NULL;

//先将数据读入结构体中
for(int i=0;i<n;i++){
scanf("%d",&address);
List[address].address = address;
scanf("%d%d",&(List[address].data),&(List[address].next));
}
//建立真正的链表
int j=0,count=0;
address = head;
while(address!=-1){
r = (Link)malloc(sizeof(point));
r->address = address;
r->data = List[address].data;
address = List[address].next;
q->next = r;
q = r;
count++;
}
q->next = NULL;
/***********************************************************************/

建立好链表之后就终于到了重头戏了。

因为是反转,所以我想到用前插法,就是把后来的结点插到之前结点的前面,每k个结点一个循环。总共有链表结点总数除以k个循环,然后剩下的链表元素直接插到后面就行了。

比如 1→2→3→4→5→6 当k为3时

6/3 = 2,所以要做两个循环。

1
2
3
4
5
6
7
8
9
10
第一次循环
第一次 1
第二次 2→1
第三次 3→2→1
结点指针要重指回 1结点
第二次循环
第一次 3→2→1→4
第二次 3→2→1→5→4
第三次 3→2→1→6→5→4
就得到了所要求的结果

逆转代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//开始逆转
int reverse_num = count/k;
Link result,temp,s;
s = result = temp =(Link)malloc(sizeof(point));
true_list = true_list->next;
temp->next = NULL;
for(int i=0;i<reverse_num;i++){
s = true_list;
for(int j=0;j<k;j++){
r=true_list;
true_list = r->next;
r->next = temp->next;
temp->next = r;
if(j==k-1)
temp = s;
}
}
//将剩余结点接上
temp = s;
temp->next = true_list;

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef struct Node{
int address;
int data;
int next;
}Node;
Node List[100000];
typedef struct point{
int address;
int data;
point *next;
}point,*Link;
int main(){
int k,n,head,address;
scanf("%d%d%d",&head,&n,&k);

Link q,true_list,r;
q = true_list = (Link)malloc(sizeof(point));
q->next = NULL;

//先将数据读入结构体中
for(int i=0;i<n;i++){
scanf("%d",&address);
List[address].address = address;
scanf("%d%d",&(List[address].data),&(List[address].next));
}
//建立真正的链表
int j=0,count=0;
address = head;
while(address!=-1){
r = (Link)malloc(sizeof(point));
r->address = address;
r->data = List[address].data;
address = List[address].next;
q->next = r;
q = r;
count++;
}
q->next = NULL;
/***********************************************************************/
//开始逆转
int reverse_num = count/k;
Link result,temp,s;
s = result = temp =(Link)malloc(sizeof(point));
true_list = true_list->next;
temp->next = NULL;
for(int i=0;i<reverse_num;i++){
s = true_list;
for(int j=0;j<k;j++){
r=true_list;
true_list = r->next;
r->next = temp->next;
temp->next = r;
if(j==k-1)
temp = s;
}
}
//将剩余结点接上
temp = s;
temp->next = true_list;
//输出结果
result = result->next;
while(result){
if(result->next!=NULL)
printf("%05d %d %05d\n",result->address,result->data,result->next->address);
else
printf("%05d %d -1\n",result->address,result->data);
result = result->next;
}
return 0;
}