7-2 Block Reversing (25分)

Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3.

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 size of a block. 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 8 371120 7 8866600000 4 9999900100 1 1230968237 6 7112033218 3 0000099999 5 6823788666 8 -112309 2 33218`

Sample Output:

71120 7 8866688666 8 0000000000 4 9999999999 5 6823768237 6 0010000100 1 1230912309 2 3321833218 3 -1

题目限度:

题目粗心:

现给定一个链表L,假设每K个位一块,最初有余K个的也为一块,当初要求将所有的块进行逆置,块内保障有序。

算法思路:

PAT的动态链表的题目,要把握其中的一个特点就是,结点的地址和数值是绑定的,next齐全不须要操心,最初将所有结点放在一片内存间断的区域天然就能够失去了。咱们这里采纳排序的办法来解决这个问题,给每一个结点赋值一个flag代表每一个结点的块号 ,id代表每一个结点初始的绝对程序,那么排序规定就是先依据flag大的进行排序,flag雷同的间接依照id进行排序即可。接下来就是flag和id的获取,对于id来说,链表的终点为0,往后顺次累加,而flag为其id/K,拍完序之后,间接输入即可,只须要留神next的输入,在最初一个结点得输入-1,否则输入下一个结点的地址就行。

留神点:

  • 1、结点不肯定都在链表上,得遍历一遍。
  • 2、地址为5位整数,得保障输入和输出一个格局。

提交后果:

AC代码:

#include<cstdio>#include<string>#include<iostream>#include<vector>#include<algorithm>using namespace std;struct Node{    int address;    int data;    int next;    int flag;// 每一个结点的块号     int id;// 每一个结点初始的绝对程序 }nodes[100005];vector<Node> list;bool cmp(const Node &a,const Node &b){    return a.flag!=b.flag?a.flag>b.flag:a.id<b.id;}int main(){    int begin,N,K;    scanf("%d %d %d",&begin,&N,&K);    Node node;    for (int i = 0; i < N; ++i) {        scanf("%d %d %d",&node.address,&node.data,&node.next);        nodes[node.address] = node;    }    int num = 0;    while(begin!=-1){        nodes[begin].id = num;        nodes[begin].flag = num/K;        ++num;        list.push_back(nodes[begin]);        begin = nodes[begin].next;    }    sort(list.begin(),list.end(),cmp);    for(int i=0;i<list.size();++i){        printf("%05d %d ",list[i].address,list[i].data);        if(i<list.size()-1){            printf("%05d\n",list[i+1].address);        } else {            printf("-1");        }    }    return 0;}