1025 反转链表 （25）（测试点1，测试点2，测试点5，测试点6）

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

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

Address Data Next

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

输出格式：

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

输入样例：

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

输出样例：

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

?这道题目有几个坑我首先说明一下：
①要看好输出用例，并不是将K个结点按照data反转就行了，反转之后还要将每个结点的next改成下一个结点的开头（测试点1不过就是因为没有注意到这个）

②并不是所有的输入用例都是有用的，题目中的输入用例是一个特殊的，最后一个元素的next是-1。也就是说在我们输入中有些是游离的结点，并不能连接到我们的链表中，所以我们需要将他舍弃。举个例子：比如输入用例中4的next是-1那么我们的 5，6就是游离的结点，我们需要将5和6舍弃（测试点2不过就是因为没有注意到这个）

③我们上面说有游离的结点，并不是只有next为-1之后的结点是游离结点，如果我们这一个链上面最后的结点的next是一个找不到的地址那还没有连接到这个链的结点也都是游离结点，举个例子：比如结点4的next为88888，但是我们并不能找到下一个地址是88888的结点，所以到这里链就断开了，后面没有连接到链上面的元素也应该被舍弃（测试点6不过就是因为没有注意到这个）

④还有就是PTA平台的测试点5是一个庞大数据输入的一个测试点，如果别的测试点都对，测试点5报运行超时，可能并不是代码的思路错误，而是代码不够精简，优化一下代码就可以。

但是我们知道PAT的考试只有3小时，如果想不到什么优化的方法降低时间复杂度，那这3分其实也不用纠结。

//完整代码
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
//链表不具有随机访问的特性，所以我们还是应当转换成数组问题

typedef struct {
    string address;
    int num;
    string next;
} node;

int main() {
    string add_first;
    int N, K;
    cin >> add_first >> N >> K;

    node List;
    vector <node> a;   //输入容器
    vector <node> b;  //利用地址排序
    for (int i = 0; i < N; i++) {
        cin >> List.address >> List.num >> List.next;
        a.push_back(List);

    }

    while (a.size()&&add_first!="-1") { //注意链表的最后一个元素不一定是-1有可能是88888这样找不到的地址，那我们while就会死循环超时
        bool istrue=true;  //链表最后的不是-1，但是是找不到，我们也需要结束while
        for (int i = 0; i < a.size(); i++) {
            if (add_first == a[i].address) {
                b.push_back(a[i]);
                add_first = a[i].next;         //这句和下面那句代码不能调换位
                a.erase(a.begin() + i);//删除a[i],但是不能用pop_back
                istrue=false;
                break;
            }
        }
        if(istrue==true)
            break;
    }

    int yu=b.size()%K;

    for(int i=0;i<b.size()-yu;i+=K){
        int begin=i;
        int end= i+K;
        reverse(b.begin()+begin,b.begin()+end);
        b[end-1].next=b[begin].next;        //反转的最后一个元素的next不一定是-1，所以如果我们全部反转后不将next变成第一个反转后索引第一个的话就产生了错误
        //比如4的结点的next为88888那么，没有上面这句话，反转后1的结点的next仍然是12309不是88888，就会错误
        
    }
    for(int i=0;i<b.size()-1;i++){
        b[i].next=b[i+1].address;
    }

    for (int i = 0; i < b.size(); i++) {
        printf("%s %d %s\n", b[i].address.c_str(), b[i].num, b[i].next.c_str());
    }

    return 0;



}

? 我的方法就是逐步将我想到的编程编出来的。

? 为了方便理解，我首先解释一下vector a?和vector?b中都是什么：

? ? vector a:这个容器中其实就是我们的输入，输入是什么样子的，那我们的vector a中就是是什么样子的。a只是为了方便排序而创建的容器。

? ? vector b:这个容器用到了两个方面首先这个容器中保存了我们升序排列的链表（在这里游离的结点以经被我们剔除了），接下来我们的vector?b中保存的是我们每K个元素反转后的链表。

typedef struct {
    string address;
    int num;
    string next;
} node;

这段代码就是定义的结点结构体。里面包含我们的结点地址，结点data,下个结点的地址next

 string add_first;
    int N, K;
    cin >> add_first >> N >> K;

    node List;
    vector <node> a;   //输入容器
    vector <node> b;  //利用地址排序
    for (int i = 0; i < N; i++) {
        cin >> List.address >> List.num >> List.next;
        a.push_back(List);

    }

接下来这一段代码就是我们的输入元素的代码，首先我们的第一行输入并不是一个结点而是链表初始地址以及输入长度以及K,接下来我们首先实例化一个结点，然后定义两个vector a b.

我们利用for循环将我们的输入利用push_back()传入我们的vector a中，这样方便我们对链表进行升序排序以及剔除游离结点。

while (a.size()&&add_first!="-1") { //注意链表的最后一个元素不一定是-1有可能是88888这样找不到的地址，那我们while就会死循环超时
        bool istrue=true;  //链表最后的不是-1，但是是找不到，我们也需要结束while
        for (int i = 0; i < a.size(); i++) {
            if (add_first == a[i].address) {
                b.push_back(a[i]);
                add_first = a[i].next;         //这句和下面那句代码不能调换位
                a.erase(a.begin() + i);//删除a[i],但是不能用pop_back
                istrue=false;
                break;
            }
        }
        if(istrue==true)
            break;
    }

这段代码是将输入的结点，按照地址寻找，首先找到第一个地址，接下来利用next找到下一个结点的地址，依次往后知道链表断开（断开的条件有两个，①next是-1，②完整遍历一遍后还是没有找到next地址对应的结点），这样我们就实现了链表按照地址连接。

int yu=b.size()%K;

    for(int i=0;i<b.size()-yu;i+=K){
        int begin=i;
        int end= i+K;
        reverse(b.begin()+begin,b.begin()+end);
        b[end-1].next=b[begin].next;        //反转的最后一个元素的next不一定是-1，所以如果我们全部反转后不将next变成第一个反转后索引第一个的话就产生了错误
        //比如4的结点的next为88888那么，没有上面这句话，反转后1的结点的next仍然是12309不是88888，就会错误
        
    }
    for(int i=0;i<b.size()-1;i++){
        b[i].next=b[i+1].address;
    }

    for (int i = 0; i < b.size(); i++) {
        printf("%s %d %s\n", b[i].address.c_str(), b[i].num, b[i].next.c_str());
    }

结点按照地址进行连接后，我们就需要完成题目中的例子了，题目说每K个进行反转，如果不足K个不需要反转。

所以在这里面我们首先将剩余的数量计算出来，计算出来之后我们就将他们的索引减去，不管他们就行啦。

在反转的实现上，我是利用reverse(b.begin()+begin,b.begin()+end);函数实现的，注意这个函数要加#include <algorithm>头文件。

?如果测试点5没有过，那我提供一个优化方法，就是并不需要reverse函数，因为我们知道reverse所需要的时间复杂度还是很高的，我们可以直接不反转，我们直接将K个元素逆序输出就行啦，这样的话我们并没有将元素反转，但是PAT只需要结果正确，这也是一个比较好的解决思路，但是也是投机取巧的方法，具体可以参照这篇文章。如果有比较好的优化方法，欢迎留下评论哦。

所有的内容都是我挨个挨个打上去的，所以有错别字也别骂我哦，最后可以要一个小小的赞嘛。?