B1025 反转链表*******

1025 反转链表 (25 分)

给定一个常数 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 行，每行格式为：

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

题目分析：

1. 未考虑创建顺序之后实际的长度值 和翻转信息后剩下的值 只拿了第一个测试点
2. 我的代码是在结构数组上排序，然后按需打印，
3. 别人的是创建坐标型数组arr嵌入坐标存数据 。 新创两个结构数组，筛查满足要求的实体放在目标结构数组shunxu中经反转fanzhuan里面。（思想）

初始错误代码如下：

#include <bits/stdc++.h>
using namespace std;
struct ddd{
    int address;
    int data;
    int next;
    int flag;
}d[100100];
bool cmp(ddd a,ddd b){
    return a.flag<b.flag;
}
int main(){
    freopen("in.txt","r",stdin);
    int index,n,k;
    cin>>index>>n>>k;
    vector<int> v;

    for(int i=0;i<n;i++){
        cin>>d[i].address>>d[i].data>>d[i].next;
    }
    int f=1;
    while(index!=-1){
        for(int i=0;i<n;i++){
            if(index==d[i].address){
                index=d[i].next;
                d[i].flag=f++;
            }
        }
    }
    sort(d,d+n,cmp);

    // cout<<n<<" "<<k<<" "<<(n/k)*k<<endl;
    for(int i=k-1;i<(n/k)*k;i+=k){
        for(int j=i;j>i-k;j--){
            if(j-1>i-k){
                printf("%05d %d %05d\n",d[j].address,d[j].data,d[j-1].address);
            }else{
                printf("%05d %d %05d\n",d[j].address,d[j].data,d[i].next);
            }
        }
    }
    int i=(n/k)*k;
    for(;i<n-1;i++){
        printf("%05d %d %05d\n",d[i].address,d[i].data,d[i].next);
    }printf("%05d %d -1\n",d[i].address,d[i].data,d[i].next);
    
    return 0;
}

别人的代码（忘记复制的那个了，我见好多都是这样）：

#include <iostream>
#include <vector>
using namespace std;
typedef struct {
    
	int adr,data,next;
}NODE;
int main()
{
    
	int head,n,k;
	cin>>head>>n>>k;
	NODE arr[100000]={
    0};
	for (int i=0; i<n; ++i) {
    
		NODE temp;
		cin>>temp.adr>>temp.data>>temp.next;
		arr[temp.adr]=temp;
	}
	vector<NODE> shunxu,fanzhuan;
	int next=head;
	while (next!=-1) {
    	//建立原本的顺序的链表
		shunxu.push_back(arr[next]);
		next=arr[next].next;
	}
	int start=0;
	//每k个反转一下 条件要小于实际链表大小 而不是n
	while (start+k-1<shunxu.size()) {
    	
		for (int i=start+k-1; i>=start; --i)
			fanzhuan.push_back(shunxu[i]);
		start+=k;
	}
	//插入剩余未反转结点 条件要小于实际链表大小 而不是n
	for (int j=start; j<shunxu.size(); ++j) 
		fanzhuan.push_back(shunxu[j]);
    
	for (next=0; next<fanzhuan.size()-1; ++next) 
		printf("%05d %d %05d\n",fanzhuan[next].adr,fanzhuan[next].data,fanzhuan[next+1].adr);
	printf("%05d %d -1\n",fanzhuan[next].adr,fanzhuan[next].data);
}

再来一个map实现的样例：

用 map 记录好首地址和值和下一节点对应关系后，将该条链表所有的节点地址放入一个数组中。而逆转时对应的下一节点地址（Next）也会发生改变，在题目中就可以处理为直接输出下一节点的地址。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 1e5 + 7;
int res[maxn];
map<int, int> dat, nxt;
int main()
{
    
    int a, n, k, tmp;
    cin >> a >> n >> k;
    int p, q;
    for(int i = 0; i < n; i++){
    
        cin >> tmp >> p >> q;
        dat[tmp] = p;
        nxt[tmp] = q;
    }
    int cnt = 0;  //有可能存在不属于这条链表的节点
    while(a != -1){
    
        res[cnt++] = a;
        a = nxt[a];
    }
    for(int i = 0; i < (cnt - cnt % k); i += k)
        reverse(res + i, res + i + k);
    for(int j = 0; j < cnt - 1; j++)
        printf("%05d %d %05d\n", res[j], dat[res[j]], res[j + 1]);  //此时输出的 Next 不再是之前的，而是重新链接后的
    printf("%05d %d -1\n", res[cnt - 1], dat[res[cnt - 1]]);
    return 0;
}

来自：https://blog.csdn.net/weixin_39040981/article/details/106509647