题目描述

链表反转，长度为k的链表需要进行k-1次相邻元素之间的反转
每一次翻转：（1）首先保存下一个节点位置t（2）然后进行翻转（3）左边节点位置右移（4）右边节点位置右移

int Reverse(int p,int k){
    //预处理
    int rear=ne[p];//保存反转之前的第一个节点作为反转之后需要拼接的最后一个节点
    int PL=ne[p];
    int PR=ne[PL];

    for(int i=0;i<k-1;i++){
        int t=ne[PR];
        ne[PR]=PL;
        PL=PR;
        PR=t;
    }
    //最后一次反转后,PL指向翻转最后一个节点，PR指向下一个节点(如果有剩余节点)
    ne[p]=PL;//对于第一次翻转，这里保存新的同节点，不再是输入数据的头节点h
    ne[rear]=PR;//翻转链原先第一个节点，翻转之后变为最后一个节点，继续拼接上后面的节点，也就是PR所指

    return rear;//rear为下一个需要反转的第一个节点，类似于第一次的空的头节点
}

统计原链表的长度cnt
从p=head;开始计数，表示从头节点也计算进去 此时进行翻转的时候应该为for(int i=0;i+k<cnt;i+=k){}
从p=ne[head];开始计数，表示长度不包括头节点，反转时候判断为 for(int i=0;i+k<=cnt;i+=k){}

翻转Reverse(int p,int k);表示从p之后的连续k个节点进行翻转

算法1

C++ 代码

#include<iostream>

using namespace std;
const int N=1e5+10;
int node[N],ne[N];

int Reverse(int p,int k){
    int rear=ne[p];//反转后的最后一个节点

    int PL=ne[p];
    int PR=ne[PL];

    for(int i=0;i<k-1;i++){
        int t=ne[PR];
        ne[PR]=PL;
        PL=PR;
        PR=t;
    }
    ne[p]=PL;  //第一个元素p=head做第一次反转后，为ne[head]=PL。此时PL是整个链表的第一个节点，而不是p
    ne[rear]=PR;//和最后剩下的元素拼接起来

    return rear;
}

int main(){

    int h,n,k;
    cin>>h>>n>>k;

    //创建空头结点
    int head,p;
    head=N-1;
    ne[head]=h;

    for(int i=0;i<n;i++){
        int addr,data,next;
        cin>>addr>>data>>next;
        node[addr]=data;
        ne[addr]=next;
    }

    //统计链表长度，每k个节点进行一次翻转
    int cnt=0;
    p=head;
    while(p!=-1){
        cnt++;
        p=ne[p];
    }

    p=head;//p=h;//p=ne[head]  i+k<=cnt
    //p指向反转节点前一个节点
    for(int i=0;i+k<cnt;i+=k){
        p=Reverse(p,k);
    }

    //输出反转后的链表
    p=ne[head];
    while(p!=-1){
        printf("%05d %d ",p,node[p]);
        if(ne[p]!=-1){
            printf("%05d\n",ne[p]);
        }else{
            cout<<-1<<endl;
        }
        p=ne[p];

    }

    return 0;
}