Reversing Linked List

问题描述

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⁵ ) 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

题意便是把链表的每K个节点反转，如果最后结尾的节点数小于K，便不需要反转
头节点格式：
[第一个数据的节点地址数据节点数反转数K]
[address N K]

其他节点内容的格式为：
[本节点地址数据下一个节点地址]
[address data next]

Notice：如果下一个节点地址（next）为-1相当于null，表示这是最后一个节点

具体如图所示：
由上方链表转为下方链表（K == 3）

image.png

解决思路

Tip：后面所说的函数都是代码里面的函数

正文：

由示例可知，题目给出数据时，节点是杂乱无章的。首先做的第一件事便是将之排序成为一个有序的链表。

这一步我的思路便是使用一个链表来接受这些数据，然后把它们排序之后放入一个队列K
使用createList() 把题目数据一股脑放到一个链表之中（无序）
使用putListToQueue()将那些数据按照地址顺序排好放在一个队列K之中

这里可能会有一个疑问，这里为什么使用队列？直接在链表上完成整个操作不可以吗？

直接在链表操作确实可以，但是！其中涉及Node的排序，反转的操作便会复杂些！而链表反转是符合栈（First in Last Out）的特性的！而且最后一个测试点还有一个坑！！（后面再说）使用链表个人会觉得变得麻烦许多，不利于思维的通畅

使用队列我们稍微改造一番也可以让队列具有栈的特性。而按顺序输出便完全符合队列的特性（First in Last out），所以只使用队列完全可以符合我们的反转，输出要求

好了，现在我们已经得到一个排序好的队列K了

下一步我们只需使reserveQueue()将队列K反转到另一个队列Q，然后把队列Q输出即可

Notice！使用reserveQueue()是把队列K元素pop到队列Q来完成反转的的！
也就是说我们把队列K每K个元素以栈的方式pop到队列Q之中，从而得到了一个已经反转好的队列！
还有一点！把队列K我们只是把每K个节点用栈的方式输出，但是我们把每K个节点（结尾不管够不够K个都算是一个节点）看成一个大的节点是按照队列的方式输出的！也就是说，局部以栈的方式pop，整体以队列的方式pop

最后使用printResult()将结果输出即可

Some Detail Of Function （里面有一些写题时的思路，有助于理解代码，便于体会

这里将讲解一些题目中的难点，以及实现该操作的函数的一些细节（建议结合代码一起看
createList：将数据放入链表，基本没什么坑，略

printResult：把队列内容输出，基本也没什么坑，唯一要注意的是最后一个节点的下一个地址是-1，不能以%05的方式输出，略

putListToQueue：作用是排序链表并将之传入队列K
我们传入初始地址（是头节点中包含的信息，第一个节点的地址），每次通过地址找到对应的节点，然后更新一下地址为该节点的next，再通过address寻找下一个节点，直到排序完整个链表。

这里需要说明一下地址：我们通过地址寻找节点，不是使用结构体的计算机地址，是格式中的address！，结构体的的计算机地址只是我们访问各个节点的桥梁

这里分享一下写这道题的有关这个函数的思路：
在代码中我使用了head->nextNode != 0作为for循环的中止条件，后面补了address != -1的终止条件。
之所以补了这个条件，便是因为测试点6的原因。测试点6导致我被卡了好久啊啊啊！！！

测试点6的意思便是，给出的数据有些Node是孤立的！也就是说，最后输出的结点数和给的结点数是不一样的！！这就导致了K有可能是大于N的！！！

这个测试点坑了我好久orz，我之前以为给出的数据会排出一个和原来结点数一样的链表（所以head->nextNode != 0作为for循环的中止条件）

因为测试点6 补了一个address != -1的终止条件，因为当address被更新到了-1表示已经排序完成。虽然本来就可以用这个条件作为终止条件，但是没有想到会出现孤立点，便没有使用

Notice：这里只是按照地址，排列好了链表

reserveQueue：将数据反转，并且连接地址
反转：每次rear前进K个元素，然后用一个变量等于rear-1，进行栈的pop来反转，length表示剩余结点数，如果小于K了，便直接顺序输出便可
Notice：
1.这里反转好了链表但是地址可能打乱了
2.反转好的元素在队列里

连接地址：如果K == 1，无需连接直接return，因为地址本身就是排好的

当K != 1直接把下一个元素的地址赋给上一个元素的next即可
不过这一块我写复杂了，是因为当时没考虑到M%K = 0的情况，直接以next->node[temp]->next != -1作为终止条件，是因为当时偷懒不想直接使用** i < lengths**作为遍历条件，而直接以找到-1作为终止条件，当M%K = 0会造成一部分元素没有连接。

而i < lengths这个条件两个情况都适配，只连接M-1个节点，最后一个节点的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;//数列长度
    int reserveNumber;//反转间隔
    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;
    //初始化队列的front and rear
    temp->front = temp->rear = 0;
    queueResult->front = queueResult->rear = 0;
    //create list
    head = createList(lenght);
    //排序数列
    putListToQueue(head, temp,nextAddress);
    //反转数列
    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

这道题还是很有难度的，尤其是测试点6！！！写了这题总体给我的感觉就是我还需要加强考虑各种漏洞（特殊情况）
像这次便导致我会有很多地方会有打补丁式的代码，便如我前面的讲解思路一样，putListToQueue() and reserveQueue()加了注水代码，只需要一个条件便可以适配，却多加了一个 if-else

虽然这个看起来挺复杂的（不过我感觉用链表更麻烦，反正我是不想怎么实现了！还有个使用三个数组来实现的，仅仅用了三十多行代码，有兴趣可以看一看https://blog.csdn.net/liyuanyue2017/article/details/83269991
）
不过利用了队列，栈，链表来实现做法，使得算法快了许多，因为在看别人的测试时间大多数都是100-200ms，这个基本在50-60ms

不过写完了这个博客突然又觉得简单好多(才怪),可能是写了博客自己总结一番的原因hhh