题目

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^5) 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

思路

  • 静态链表结构Lnode{int data, int next}
  1. 建立一个静态链表 Node[$10^{5}$] 存储结点，下标即地址
  2. 读取第一个地址,结点个数 N，需要颠倒的长度 K
  3. 建立一个int数组 sum[N]，从初始地址开始在 Node 数组里一路找下去，同时把下标地址存入数组 sum，计算在链表上的结点数 j
  4. 比较 K 和 j 的大小，够换则进循环交换，使用 low=i 和 high=i+K (high不参与交换，因为i到i+K的结点数是K+1)来从两端向中间开始互换
  5. 输出 sum[N] 是结点地址，Node[sum[N]] 是数值，sum[N+1] 是链表next地址
  6. 最后一个节点的next地址输出-1

源码实现

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct Nodes {
    int data;
    int next;
}Node[100000];

int rev(int a[],int low,int high);

int main()
{
    int Add,N,K;
    scanf("%d %d %d",&Add,&N,&K);
    int sum[N];
    int a,j=0;
    for(int i=0;i<N;i++){
        scanf("%d",&a);
        scanf("%d %d",&(Node[a].data),&(Node[a].next));
    }
    while(Add!=-1){
        sum[j]=Add;
        j++;
        Add=Node[Add].next;
    }
    int k=0;
    while(k+K<=j){
        rev(sum,k,k+K);
        k=k+K;
    }
    int i=0;
    for(i=0;i<j-1;i++)
    {
        printf("%05d %d %05d\n",sum[i],Node[sum[i]].data,sum[i+1]);
    }
     printf("%05d %d -1\n",sum[i],Node[sum[i]].data);
     return 0;
}

int rev(int a[],int low,int high)
{
    int temp;
    high=high-1;
    while(low<high){
        temp=a[low];
        a[low]=a[high];
        a[high]=temp;
        low++;
        high--;
    }
    return 0;
}

本题的坑

  • 所给的结点不一定都在链表上，所以需要在排序时计算结点数
  • 所给数据可能过大，需要考虑时间复杂度

吐槽和感想

一开始在下打算使用链表来做，结果做完后发现过不去测试点5，因为时间复杂度达到了$n^{2}$，而且没有考虑到有的结点不属于链表里，导致测试点6也没过

这点道题其实思路非常好想，奈何在下的程序设计基础没有打好,写程序的过程也会突然短路。在写程序的过程中出现了很多啼笑皆非的场景，譬如竟然会出现把while循环写成了if，导致交换一次就停了下来，依照思路排查半天没有结果，最后发现是程序写错了…