02-线性结构3 Reversing Linked List (25 分)

02-线性结构3 Reversing Linked List (25 分)

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 (≤10
​5
​​ ) 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:

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:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

<mark>谷歌翻译：</mark>
给定常数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。

输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行包含第一个节点的地址，正N（≤10
五
）是节点的总数，以及正K（≤N），它是要反转的子列表的长度。节点的地址是5位非负整数，NULL由-1表示。

然后是N行，每行描述一个格式的节点：

地址数据接下来
其中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个数进行倒序存储，不够k时则退出。链表以负一为结束。

可以用数组来结构体存储来存储值和当前值得下一个地址。数组下标存储该值得地址。

用while循环将下标从第一个一直遍历到-1为止，因为里面可能有多余的值并不在链表上。每次循环就将当前值得地址进行存储，其下标从小到大构成一个链。

然后进行k次翻转，继续用while循环，直到当前位置加k大于总个数时，退出。反转有一个algorithm库的函数reverse（）。
<mark>eg</mark>：reverse(&num[i],&num[i+k]);
<mark>其意思是</mark>：从下标为i开始讲其后的k个数进行反转。

<mark>**拓展：reverse()函数</mark>
参考官网链接：http://www.cplusplus.com/reference/algorithm/reverse/
根sort用法基本相近，最常用两个参数时，第一个为起点地址，第二个为操作的数目。
eg1：reverse（a,a+10）; 类似于sort。
eg2：reverse (&a[3],&a[3+5]);为从下标三开始的五个数，进行反转。

<mark>注意</mark>：num数组存储的其实就是顺序，所以输出时可以直接用num[i]进行遍历。但是，为了格式的好处理，尽量将最后一个地址为-1 的进行单独输出。

<mark>困惑</mark>：
1、 不清楚为何这样写不能通过全部样例。

  //没明白为何这样不行，不能通过所有样例
//    int temp=j;
//    j=0;
//    while(temp>=k)
//    {
//        reverse(&num[j],&num[j+k]);//翻转函数，翻转j往后的k个元素
//
//        temp-=k;j+=k;
//    }

2、按理说没有毛病，但是总是不对，用结构体数组存储的下一个地址，进行遍历，应该没有问题，但是就是不对。。。

//不明白为何下面的注释不行，非得写成num[i+1]
        //printf("%05d %d %05d\n",num[i],arr[num[i]].Data,arr[num[i]].NextAddress);
        printf("%05d %d %05d\n",num[i],arr[num[i]].Data,num[i+1]);

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 1000005
#define mod 7654321

struct Node
{
    int Data;
    int NextAddress;
}arr[maxn];//下标存储当前节点的地址

int num[maxn];//存储链表中的每个节点的地址

int main()
{
    int first,n,k;
    int add,data,next;
    cin>>first>>n>>k;

    for(int i=0;i<n;i++)
    {
        cin>>add>>data>>next;
        arr[add].Data=data;
        arr[add].NextAddress=next;
    }

    int p=first,j=0;
    while(p!=-1)//p=-1时结束链表
    {
        num[j++]=p;//存储链表中的每个节点的地址
        p=arr[p].NextAddress;//指向当前节点的下一个节点的地址
    }

    //没明白为何这样不行，不能通过所有样例
// int temp=j;
// j=0;
// while(temp>=k)
// {
// reverse(&num[j],&num[j+k]);//翻转函数，翻转j往后的k个元素
//
// temp-=k;j+=k;
// }

    int i=0;

	while(i+k<=j)
	{
		reverse(&num[i],&num[i+k]);
		i=i+k;
	}

    for(int i=0;i<j-1;i++)
    {
        //不明白为何下面的注释不行，非得写成num[i+1]
        //printf("%05d %d %05d\n",num[i],arr[num[i]].Data,arr[num[i]].NextAddress);
        printf("%05d %d %05d\n",num[i],arr[num[i]].Data,num[i+1]);
    }
    printf("%05d %d -1\n",num[j-1],arr[num[j-1]].Data);

    return 0;
}