前言

在准备考研复习专业课数据结构，所以我在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;
}