题135.pta数据结构题集-02-线性结构3 Reversing Linked List (25 分)

一、题目

在这里插入图片描述

二、题解

碰到这个数并不大的节点地址问题，其实用数组下标来表示地址是完全没问题的，所以我们用data0，next0，re_next来存储下标对应地址的节点信息。之后遍历链表，将节点入栈，入队，当节点数达到逆转数目时节点全出栈，将信息存到对应地址的re_next数组里，最后看是把队列的节点接上还是把栈中的节点接上就好(依然看逆转数目是否达到逆转节点数目)。

#include <bits/stdc++.h>

using namespace std;

int data0[100000],next0[100000];//下标表示地址，用data表示相应位置的数据，next0表示相应位置的下一个节点地址
int re_next[100000];//用re_next表示逆转链表的每个节点的下一个节点的地址

int main()
{

    int address0;
    int N,K;
    cin>>address0>>N>>K;
    for(int i=0; i<N; i++)
    {
        int address;
        cin>>address;
        cin>>data0[address]>>next0[address];
    }
    stack<int> s;
    queue<int> q;
    int address=-1,address00=-1;
    s.push(address0);
    q.push(address0);
    while(next0[address0]!=-1)
    {
        if(s.size()==K)
        {
            if(address==-1)//针对表头
            {
                address00=address=s.top();
                s.pop();
                q.pop();
            }
            while(!s.empty())
            {
                re_next[address]=s.top();
                address=s.top();
                s.pop();
                q.pop();
            }
        }
        address0=next0[address0];
        s.push(address0);
        q.push(address0);
    }
    if(s.size()==K)//针对上面的那个循环退出之前做的最后一次入栈操作，看看加上这次是否满足逆转个数
    {
        if(address==-1)
        {
            address00=address=s.top();
            s.pop();
            q.pop();
        }
        while(!s.empty())
        {
            re_next[address]=s.top();
            address=s.top();
            s.pop();
            q.pop();
        }
    }
    else//若不满足逆转个数则直接顺序连接，用队列里头的节点
    {
        if(address==-1)
        {
            address00=address=s.top();
            s.pop();
            q.pop();
        }
        while(!q.empty())
        {
            re_next[address]=q.front();
            address=q.front();
            s.pop();
            q.pop();
        }
    }
    re_next[address]=-1;
    while(re_next[address00]!=-1)
    {
        printf("%05d %d %05d\n",address00,data0[address00],re_next[address00]);
        address00=re_next[address00];
    }
    printf("%05d %d -1\n",address00,data0[address00],re_next[address00]);
}

/*
//全逆转
00100 6 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
*/