PAT乙级1025 || 反转链表（详解，C/C++示例，测试点分析）

Posted on In

反转链表

题目描述

给定一个常数 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 (≤$10^5$)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。

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

1
Address Data Next

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

输出格式

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

输入样例

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

输出样例

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

问题解决

解题思想

本题要处理的细节较多。首先，单链表可采用静态链表的存储结构（当然也可以选择用指针的链式结构），定义一个结构体数组，下标为当前结点地址，两个成员分别是结点数据和下一个结点的地址；然后，需要统计输入的有效结点个数cou_n，cou_n / k即为需要反转的组数（也为调用反转函数的次数）；
以下几点容易忽略：

  • 统计输入的有效结点个数。若用n / k来表示需要反转的次数，则导致PATOJ的最后一个测试点不通过。
  • 输出格式的控制。除了最后的-1外，其它地址都是5位非负整数，不足5位的左侧要补0。
  • 反转时第一组结点需要特殊处理。第一组结点反转后的第一个结点即为整个链表的第一个结点，需要记录下来，以便输出。
  • 头插法反转防断链处理。采用头插法反转链表，需要设置一个指针指向待处理结点的下一个结点，否则会因断链而无法到达下一个结点。

知识拓展

我们知道在C语言中，要想通过函数来改变变量的值，只通过值传递参数的形式是不能实现的，我们要通过地址传递的方式，比如数组，指针。而在C++中，我们有更为简便的方式——引用，引用相当于给对象取一个别名，通过该别名，我们可以对该对象进行相关操作，并可对主调函数的相应实参进行修改，使用时，在形参名前面加一个&符号即可(例如本题的函数形参中的addre_start，它与实参addre_start[0]对应，改变addre_start的值相应的addre_start[0]的值也会改变)。关于引用的更多讲解，大家可暂时查看C++相关书籍等。

代码示例（C/C++）

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
#include <cstdio>
#define MAXN 100000
using namespace std;
void Reverse_K(struct node Link_node[],int &addre_start,int k);
//单链表结点
struct node
{
    int data;//结点数据
    int next;//下一个结点地址
}Link_node[MAXN];//下标为当前结点地址
int main()
{
    int addre,n,k;//addre为第 1 个结点的地址
    scanf("%d%d%d",&addre,&n,&k);//第一行输入
    int address;//暂存输入的地址
    for(int i = 0; i < n; i++){
        scanf("%d",&address);//当前结点地址
        //当前结点数据及下一个结点地址
        scanf("%d%d",&Link_node[address].data,&Link_node[address].next);
    }
    int addre_start[2],addre_end;
    addre_start[0] = addre;
    int cou_n = 0;//统计有效的结点个数
    while(addre != -1){
        cou_n++;
        addre = Link_node[addre].next;
    }
    int flag = 1;//标记第一次反转后的第一个结点(即为整个单链表的第一个结点)
    for (int i = 0; i < cou_n / k; i++){//需要进行n / k次的反转
        if(flag){//第一组k个结点特殊处理
            addre_end = addre_start[0];
            Reverse_K(Link_node,addre_start[0],k);
            addre = addre_start[0];
            flag = 0;
        }
        else{
            addre_start[0] = Link_node[addre_end].next;
            addre_start[1] = addre_start[0];//暂存当前待处理k个结点的第一个结点，反转后其将变为最后一个结点
            Reverse_K(Link_node,addre_start[0],k);
            Link_node[addre_end].next = addre_start[0];
            addre_end = addre_start[1];
        }
    }
    while(addre != -1){//注意输出格式控制
        if(Link_node[addre].next != -1){
            printf("%05d %d %05d\n",addre,Link_node[addre].data,Link_node[addre].next);
        }
        else{
            printf("%05d %d %d\n",addre,Link_node[addre].data,Link_node[addre].next);
        }
        addre = Link_node[addre].next;
    }
    return 0;
}
//头插法实现链表反转，通过C++的引用&来返回值，addre_start传入为
//当前待处理的一组k个结点中的第一个结点，返回为反转后的第一个结点
void Reverse_K(struct node Link_node[],int &addre_start,int k)//注意是Link_node[]，而非Link_node
{
    int addre_s = addre_start;//暂存反转前的第一个结点地址
    int p = Link_node[addre_start].next;//p指向下一个结点，防止断链
    int q;//q指向当前待处理结点
    for(int i = 1;i < k; i++){//k个结点要进行k-1次链的反指向
        q = p;
        p = Link_node[p].next;//p指向下一个结点，防止断链
        Link_node[q].next = addre_start;//反转
        addre_start = q;//当前的第一个结点的地址
    }
    Link_node[addre_s].next = p;//反转后第一个结点变成最后一个结点，让其指向下一组待反转的首结点
}

题目来源：PAT乙级1025
作者：CHEN, Yue
单位：浙江大学

稀罕作者