【L2-022 重排链表】天梯赛L2系列详细解答

天梯赛L2-022 重排链表 题目详情：

输入样例：

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

思路:

写这个题呢?需要回顾一下L2-002 链表去重这两个题目一个意思。

写法大同小异。

由于我是倒着整理L2的。

这里就先写下这个题目的思路。

先这个题目的输入:

第一行：起始地址，结点总数N
接下来N行：结点地址，结点的数据，下一个结点的地址

题目的最后要求是什么呢？就是让你把这些输入进来的链表，按照它重新规定的顺序排下来，然后输出。

说是链表题目，但是都把地址给我们了，所以我们大可以用结构体，用结构体存下所有的数据。

struct Lnode
{
    int address;
    int data;
    int next;
}p[maxn];

那我们接下来要怎么输出呢？顺序怎么搞？因为它重新规定的顺序：n→1→n−1→2→⋯
我的思路是什么样子呢？
根据数学关系：先输出b[n-1],在输出b[0],然后又输出b[n-2],再输出b[1]，循环着来。

一个一个接着来把他们都输出出来。

所以要怎么办，先把他们原来的顺序找到，存到一个b数组里面，然后是我们就可以输出啦，先输出b[n-1],在输出b[0],然后又输出b[n-2],再输出b[1]。

就按照这个关系输出结果。

到了最后一个结点，我们跳出这个循环，单独输出最后一个结点的信息，因为最后一个地址是-1的。

详细代码:

#include
using namespace std;
const int maxn = 1e5 + 5;
struct Lnode
{
    int address;
    int data;
    int next;
 }a[maxn];
int first,n;
int b[maxn];//存放链表原来的顺序
int main()
{
    cin>>first>>n;
    int m1,m2,m3;
    for(int i = 1; i <= n; i++)//输入链表 
    {
        cin>>m1>>m2>>m3;
        a[m1].address = m1;
        a[m1].data = m2;
        a[m1].next = m3;
    }
    int i = first, j = 0;
    while(a[i].next != -1) //要记住：最后一个元素的地址没有被存到b数组中 
    {
        b[j] = i;
        j++;
        i = a[i].next;
    }
    b[j] = a[i].address;//存最后一个元素的地址 
    int count = 1;//控制输出个数以及控制输出前面还是后面
    
    for(int k = 0; k < j/2 + 1; k++)
    {//控制好k的大小，因为要用k前面提到的数学关系
        if(count % 2 != 0)//奇数输出后面
        {
            printf("%05d %d %05d\n", a[b[j-k]].address, a[b[j-k]].data, a[b[k]].address);
            //%05d是为了控制格式，按照题目的输出要求，先输出自己的地址，然后自己的值，最后输出下一个结点的地址
            k--;//为什么要k--？
            //因为是先输出后面b[n-k]，所以下一次要输出前面b[k]了
            //这个时候如果k++，那么k的大小就变了，所以要k--，让k不变
        }
        else //偶数输出前面 
            printf("%05d %d %05d\n", a[b[k]].address, a[b[k]].data, a[b[j-1-k]].address);
        count++;
        if(count > j)//如果该输出最后一个的时候，跳出来，另外输出 
            break;
    }
    printf("%05d %d -1\n", a[b[j/2]].address, a[b[j/2]].data);//最后一个元素肯定是在原来链表的中间位置
    
    return 0;
}

知识总结:

这个题说得不是很清楚，这种算法有点low，尤其是数学关系那块，感觉自己说不明白那个意思。

有可以完善的地方，希望大家可以指出来。