這個測試點(diǎn)坑了我好久orz，我之前以為給出的數(shù)據(jù)會排出一個和原來結(jié)點(diǎn)數(shù)一樣的鏈表（所以head->nextNode != 0作為for循環(huán)的中止條件）

因?yàn)闇y試點(diǎn)6 補(bǔ)了一個address != -1的終止條件，因?yàn)楫?dāng)address被更新到了-1表示已經(jīng)排序完成。雖然本來就可以用這個條件作為終止條件，但是沒有想到會出現(xiàn)孤立點(diǎn)，便沒有使用

Notice：這里只是按照地址，排列好了鏈表

reserveQueue：將數(shù)據(jù)反轉(zhuǎn)，并且連接地址
反轉(zhuǎn)：每次rear前進(jìn)K個元素，然后用一個變量等于rear-1，進(jìn)行棧的pop來反轉(zhuǎn)，length表示剩余結(jié)點(diǎn)數(shù)，如果小于K了，便直接順序輸出便可
Notice：
1.這里反轉(zhuǎn)好了鏈表但是地址可能打亂了
2.反轉(zhuǎn)好的元素在隊(duì)列里

連接地址：如果K == 1，無需連接直接return，因?yàn)榈刂繁旧砭褪桥藕玫?/p>

當(dāng)K != 1直接把下一個元素的地址賦給上一個元素的next即可
不過這一塊我寫復(fù)雜了，是因?yàn)楫?dāng)時(shí)沒考慮到M%K = 0的情況，直接以next->node[temp]->next != -1作為終止條件，是因?yàn)楫?dāng)時(shí)偷懶不想直接使用** i < lengths**作為遍歷條件，而直接以找到-1作為終止條件，當(dāng)M%K = 0會造成一部分元素沒有連接。

而i < lengths這個條件兩個情況都適配，只連接M-1個節(jié)點(diǎn)，最后一個節(jié)點(diǎn)的next直接寫-1，但是我懶得改了，希望沒有讓你們感到誤解，困惑

image.png

Code

#include<stdio.h>
#include<malloc.h>
#define size 100000
typedef struct node {
    int address;
    int data;
    int next;
    struct node* nextNode;
}Node, *Pnode;
typedef struct queue {
    Pnode node[size+1];
    int front;
    int rear;
}Queue,*Pqueue;
Pnode createList(int lenght);
void putListToQueue(Pnode head, Pqueue queue, int address);
void reserveQueue(Pqueue first, Pqueue next, int reserveNumber, int length);
void printResult(Pqueue queue);
int main(void) {
    Node iniInformation;
    int lenght;//數(shù)列長度
    int reserveNumber;//反轉(zhuǎn)間隔
    int nextAddress;//address of next node
    Pnode head = 0;
    Pqueue queueResult = (Pqueue)malloc(sizeof(Queue));
    Pqueue temp = (Pqueue)malloc(sizeof(Queue));
    scanf("%d %d %d", &iniInformation.address, &iniInformation.data, &iniInformation.next);
    lenght = iniInformation.data;
    reserveNumber = iniInformation.next;
    nextAddress = iniInformation.address;
    //初始化隊(duì)列的front and rear
    temp->front = temp->rear = 0;
    queueResult->front = queueResult->rear = 0;
    //create list
    head = createList(lenght);
    //排序數(shù)列
    putListToQueue(head, temp,nextAddress);
    //反轉(zhuǎn)數(shù)列
    reserveQueue(temp, queueResult, reserveNumber, temp->front - temp->rear);
    //output result
    printResult(queueResult);
    return 0;
}
Pnode createList(int lenght) {
    Pnode temp = 0;
    Pnode head = temp = (Pnode)malloc(sizeof(Node));

    for (int i = 0; i < lenght; i++) {
        Pnode node = (Pnode)malloc(sizeof(Node));
        scanf("%d %d %d", &node->address, &node->data, &node->next);
        temp->nextNode = node;
        temp = node;
        temp->nextNode = 0;
    }
    return head;
}
void printResult(Pqueue queue) {
    Pnode node = 0;
    for (;queue->rear != queue->front;) {
        node = queue->node[queue->rear];
        if (node->next != -1) {
            printf("%0.5d %d %0.5d\n", node->address, node->data, node->next);
        }else{
            printf("%0.5d %d %d", node->address, node->data, node->next);
        }
        queue->rear++;
    }
}
void putListToQueue(Pnode head, Pqueue queue, int address) {
    Pnode temp = 0; 
    for (; head->nextNode != 0;) {
        temp = head;
        for (;temp->nextNode != 0 && temp->nextNode->address != address;) {
            temp = temp->nextNode;
        }
        address = temp->nextNode->next;
        queue->node[queue->front++] = temp->nextNode;
        temp->nextNode = temp->nextNode->nextNode;
        if (address == -1) {
            break;
        }
    }
}
void reserveQueue(Pqueue first, Pqueue next, int reserveNumber, int length) {
    int temp;
    int lengths = length;
    for (; length > 0;) {
        if (length >= reserveNumber) {
            first->rear += reserveNumber;
            temp = first->rear  - 1;
            for (int i = 0; i < reserveNumber; i++) {
                next->node[next->front++] = first->node[temp--];
            }
        }else{
            for (;first->rear != first->front;) {
                next->node[next->front++] = first->node[first->rear++];
            }
        }
        length -= reserveNumber;
    }
    if (reserveNumber == 1) {
        return;
    }
    temp = next->rear;
    if (lengths % reserveNumber == 0)
    {
        for (int i = 1; i < lengths; i++, temp++)
        {
            next->node[temp]->next = next->node[temp + 1]->address;
        }
        next->node[temp]->next = -1;
    }else{
        for (; next->node[temp]->next != -1; temp++) {
            next->node[temp]->next = next->node[temp + 1]->address;
        }
    }
}

Summary

這道題還是很有難度的，尤其是測試點(diǎn)6！?。懥诉@題總體給我的感覺就是我還需要加強(qiáng)考慮各種漏洞（特殊情況）
像這次便導(dǎo)致我會有很多地方會有打補(bǔ)丁式的代碼，便如我前面的講解思路一樣，putListToQueue() and reserveQueue()加了注水代碼，只需要一個條件便可以適配，卻多加了一個 if-else

雖然這個看起來挺復(fù)雜的（不過我感覺用鏈表更麻煩，反正我是不想怎么實(shí)現(xiàn)了！還有個使用三個數(shù)組來實(shí)現(xiàn)的，僅僅用了三十多行代碼，有興趣可以看一看https://blog.csdn.net/liyuanyue2017/article/details/83269991
）
不過利用了隊(duì)列，棧，鏈表來實(shí)現(xiàn)做法，使得算法快了許多，因?yàn)樵诳磩e人的測試時(shí)間大多數(shù)都是100-200ms，這個基本在50-60ms

不過寫完了這個博客突然又覺得簡單好多(才怪),可能是寫了博客自己總結(jié)一番的原因hhh