526互联

PAT Basic 1110. 区块反转

发布时间 2023-04-18 20:44:21作者: 十豆加日月

PAT Basic 1110. 区块反转

1. 题目描述：

给定一个单链表 \(L\)，我们将每 \(K\) 个结点看成一个区块（链表最后若不足 \(K\) 个结点，也看成一个区块），请编写程序将 \(L\) 中所有区块的链接反转。例如：给定 \(L\) 为 \(1→2→3→4→5→6→7→8\)，\(K\) 为 3，则输出应该为 \(7→8→4→5→6→1→2→3\)。

2. 输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 \(N\) (\(≤10^5\))、以及正整数 \(K\) (\(≤N\))，即区块的大小。结点的地址是 5 位非负整数，NULL 地址用 \(−1\) 表示。

接下来有 \(N\) 行，每行格式为：

Address Data Next

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

3. 输出格式：

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

4. 输入样例：

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

5. 输出样例：

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

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

回血题，定义结构体Node存储结点相关信息，因为结点地址为5位非负整数，所以地址属于闭区间\([00000,99999]\)，根据地址个数定义结构体数组allNode存储所有结点信息，list存储原始链表，res存储结果链表。先根据头结点地址构造出原始链表，然后根据题意构造结果链表并输出即可，构造结果链表要根据原始链表结点个数能否被 \(K\) 整除分情况进行处理。这类题目的套路都是将链表进行顺序存储，方便进行随机访问，已经做麻了。。。

My Code:

#include <stdio.h>

#define MAX_ADDRESS 100000

typedef struct node
{
    int address;
    int data;
    int next;
} Node;

int main(void)
{
    int pHead=0, nodeCount=0, k=0;
    Node allNode[MAX_ADDRESS];
    Node list[MAX_ADDRESS];
    int activeCount=0;
    Node res[MAX_ADDRESS];
    int i=0, j=0; // iterator
    int tempAdr=0, tempData=0, tempNext=0;
    int pNode=0; // pointer of Node
    int groupNum = 0;
    int resCount=0;
    
    scanf("%d%d%d", &pHead, &nodeCount, &k);
    for(i=0; i<nodeCount; ++i)
    {
        scanf("%d%d%d", &tempAdr, &tempData, &tempNext);
        allNode[tempAdr].address = tempAdr;
        allNode[tempAdr].data = tempData;
        allNode[tempAdr].next = tempNext;
    }
    
    pNode = pHead; // construct original linklist
    while(pNode != -1)
    {
        list[activeCount++] = allNode[pNode];
        pNode = allNode[pNode].next;
    }
    
    groupNum = activeCount/k;
    
    resCount=0; // res index
    if(activeCount % k) // have remain node
    {
        for(i=k*groupNum; i<activeCount; ++i)
        {
            res[resCount++]=list[i];
        }
        
        for(i=(groupNum-1)*k; i>=0; i-=k)
        {
            for(j=0; j<k; ++j)
            {
                res[resCount++] = list[i+j];
            }
        }
    }
    else // doesn't have remain node
    {
        for(i=(groupNum-1)*k; i>=0; i-=k)
        {
            for(j=0; j<k; ++j)
            {
                res[resCount++] = list[i+j];
            }
        }
    }
    
    for(i=0; i<resCount-1; ++i)
    {
        printf("%05d %d %05d\n", res[i].address, res[i].data, res[i+1].address);
    }
    printf("%05d %d -1\n", res[i].address, res[i].data);
    
//     for(i=0; i<activeCount; ++i) // output original list
//     {
//         printf("%d %d %d\n", list[i].address, list[i].data, list[i].next);
//     }
    
    return 0;
}