PAT（甲级）2019年冬季考试 7-2 Block Reversing (25分)——模拟链表

╰半夏微凉° 2023-02-19 10:25 21阅读 0赞

## 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 3
    71120 7 88666
    00000 4 99999
    00100 1 12309
    68237 6 71120
    33218 3 00000
    99999 5 68237
    88666 8 -1
    12309 2 33218

Sample Output:

71120 7 88666
    88666 8 00000
    00000 4 99999
    99999 5 68237
    68237 6 00100
    00100 1 12309
    12309 2 33218
    33218 3 -1

## 题意： ##

给定一个单链链表L，让我们把每个K个节点看作一个块（如果列表末尾的节点少于K个，那么其余的节点仍然被看作一个块）。你的工作是反转L中的所有块。例如，给定L为1→2→3→4→5→6→7→8和K为3，你的输出必须是7→8→4→5→6→1→2→3。

输入规格：  
每个输入文件包含一个测试用例。对于每种情况，第一行包含第一节点的地址、节点总数的正N（≤105）和块大小的正K（≤N）。节点的地址是一个5位非负整数，空值由-1表示。

接下来是N行，每行描述一个节点的格式为

Address Data Next

其中Address是节点的位置，Data是整数，Next是下一个节点的位置。  
输出规格：  
对于每种情况，输出结果的有序链表。每个节点占用一行，并以与输入相同的格式打印。

## 代码： ##

1.　解法一（来源于网络）  
使用sort的方法巧妙将链表反转：三阶排序：1.is0k 2.group 3.index  
对于这道题来说，主要是group比较重要，在Node的结构里直接加入\{group、index\}，初始化后进行排序！

#include <cstdio>
    #include <algorithm>
    #include <vector>
    using namespace std;
    struct Node { 
    	int data,address,next;
    	int isOk;
    	int group, index;
    	Node (){ 
    		isOk=0;
    	}
    }node[100010];
    bool cmp(Node a, Node b){ 
    	if (a.isOk!=b.isOk) return a.isOk>b.isOk;
    	else if (a.group!=b.group) return a.group>b.group;
    	else return a.index<b.index;
    }
    int main(){ 
    	int n,k;
    	int begin;
    	scanf("%d %d %d",&begin, &n, &k);
    	for (int i=0; i<n; i++){ 
    		int address, data, next;
    		scanf("%d %d %d",&address, &data, &next);
    		node[address].data=data;
    		node[address].address=address;
    		node[address].next=next;
    	}
    	int p=begin;
    	int cnt=0;
    	//group a[group][index]
    	while (p!=-1){ 
    		node[p].group=cnt/k;
    		node[p].index=cnt%k;
    		cnt++;
    		node[p].isOk=1;
    		p=node[p].next;
    	}
    	sort(node, node+100010, cmp);
    	for (int i=0; i<cnt; i++){ 
    		if (i!=cnt-1){ 
    			printf("%05d %d %05d\n",node[i].address, node[i].data, node[i+1].address);
    		}else { 
    			printf("%05d %d -1\n",node[i].address, node[i].data);
    		}
    	}
    	return 0;
    }

2.　解法二（来源于网络）

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 100010;
    
    struct Node
    { 
        int data, nex;
    }node[maxn];
    
    
    void Print(const vector<int> & ans)
    { 
        if(ans.size() == 0)
        { 
            printf("0 -1");
        }else
        { 
            for(int i = 0; i < ans.size(); ++i)
            { 
                if(i < ans.size() - 1) printf("%05d %d %05d\n", ans[i], node[ans[i]].data, ans[i+1]);
                else printf("%05d %d -1\n", ans[i], node[ans[i]].data);
            }
        }
    }
    
    int main()
    { 
        int first, n, k;
        scanf("%d %d %d", &first, &n, &k);
        for(int i = 0; i < n; ++i)
        { 
            int ad;
            scanf("%d", &ad);
            scanf("%d %d", &node[ad].data, &node[ad].nex);
        }
        int head = first, cnt = 1;
        vector<vector<int> > tmp;
        vector<int> tmp2, ans;
        while(head != -1)
        { 
            tmp2.push_back(head);
            if(cnt % k == 0 || node[head].nex == -1)
            { 
                tmp.push_back(tmp2);
                tmp2.clear();
            }
            cnt++;
            head = node[head].nex;
        }
        for(int i = tmp.size()-1; i >= 0; --i)
        { 
            for(int j = 0; j < tmp[i].size(); ++j)
            { 
                ans.push_back(tmp[i][j]);
            }
        }
        Print(ans);
        return 0;
    }

3.　解法三（来源于网络）

#include<cstdio> 
    #include<iostream> 
    #include<vector> 
    #include<map>
    #include<string>
    #include<set>
    #include<cctype>
    #include<algorithm>
    using namespace std;
    const int INF = 0x3fffffff;
    const int maxn = 100010;
    struct node{ 
    	int address,data,next,flag;
    	node(){ 
    		flag = -1;
    	}
    }Node[maxn];
    bool cmp1(node a,node b){ 
    	return a.flag > b.flag;
    }
    bool cmp2(node a,node b){ 
    	return a.flag < b.flag;
    }
    int main(){ 
    	int start,n,k;
    	scanf("%d%d%d",&start,&n,&k);
    	for(int i = 0; i < n; i++){ 
    		int add;
    		scanf("%d",&add);
    		scanf("%d%d",&Node[add].data,&Node[add].next);
    		Node[add].address = add;
    	}
    	int cnt = 0;
    	for(int p = start; p != -1; p = Node[p].next){ 
    		Node[p].flag = cnt++;
    	}
    	sort(Node,Node+maxn,cmp1);
    	int temp = cnt % k;
    	if(temp != 0){ 
    		sort(Node,Node+temp,cmp2);
    	}
    	for(int i = temp; i + k <= cnt; i+=k){ 
    		sort(Node+i,Node+i+k,cmp2);
    	}
    	for(int i = 0; i < cnt; i++){ 
    		if(i != cnt - 1)
    			printf("%05d %d %05d\n",Node[i].address,Node[i].data,Node[i+1].address);
    		else printf("%05d %d -1\n",Node[i].address,Node[i].data);
    	}
    }